# Tag Info

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