8

The paper J.-M. Autebert, Une note sur le cylindre des langages déterministes, Theoretical Computer Science 8 (1979), 395-399 gives a short proof of the following result (credited to Greibach) which seems to answer your question: there is no deterministic context-free language $L$ such that, for every deterministic context-free language $C$, there ...


8

There actually is a hardest DCFL, which is a deterministic version of Greibach's; it was introduced by Sudborough in 78 in On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store—it is however hardest w.r.t log-space reduction. The language $L_0^{(2)}$ referred therein is the set of words over $...


8

An identical homomorphism characterization of DCFL does not seem to be possible. The following is extracted from Greibach's original paper. We show that every context-free language can be expressed as $h^{-1}(L_0)$ or $h^{-1}(L_0-\{e\})$ for a homomorphism $h$. The algebraic statement is: the family of context-free languages is a principal AFDL; ... By ...


7

In general one would not expect random instances of SAT to have bounded treewidth, even if they are easy. Here is an example: A random k-SAT instance on $n$ variables where each variable occurs in $3$ clauses will be an expander graph, and therefore have treewidth $\theta(n)$ with high probability. This holds in the model where we fix an n and an m (with ...


4

If P=NP, then all NP-complete problems are equally difficult from the perspective of polynomial-time reductions. On the other hand, if P!=NP, then we have ways to differentiate NP-complete problems, for example: Approximable problems - NP-complete problems where we can find a polynomial-time algorithm that gives us almost the desired answer (within a ...


Only top voted, non community-wiki answers of a minimum length are eligible