The Hardest Context-Free Language
From MaRDI portal
Publication:4404463
DOI10.1137/0202025zbMath0278.68073OpenAlexW1996878052MaRDI QIDQ4404463
Publication date: 1973
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0202025
Related Items
Sur la structure des langages algébriques ⋮ On morphic generation of regular languages ⋮ The hardest \(\operatorname{LL}(k)\) language ⋮ On purely morphic characterizations of context-free languages ⋮ Une note sur le théorème de caractérisation des générateurs algébriques. (A note on the characterization theorem for context-free generators) ⋮ Self-reducibility ⋮ Parallel complexity of logical query programs ⋮ Unnamed Item ⋮ Some subclasses of context-free languages in \(NC^ 1\) ⋮ Unnamed Item ⋮ Weighted hypertree decompositions and optimal query plans ⋮ Unnamed Item ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Restrictions and representations of vector controlled concurrent system behaviours ⋮ The hardest language for grammars with context operators ⋮ Langages sur des alphabets infinis ⋮ McNaughton families of languages. ⋮ On Second-Order Monadic Groupoidal Quantifiers ⋮ The Hardest LL(k) Language ⋮ On the complexity of regular-grammars with integer attributes ⋮ Knapsack in graph groups ⋮ Formes de langages et de grammaires ⋮ A hardest language recognized by two-way nondeterministic pushdown automata ⋮ Monadic Thue systems ⋮ On eliminating nondeterminism from Turing machines which use less than logarithm worktape space ⋮ A note on morphic characterization of languages ⋮ On hardest languages for one-dimensional cellular automata ⋮ Nonuniform complexity and the randomness of certain complete languages ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Complexity in left-associative grammar ⋮ On the complexity of finite, pushdown, and stack automata ⋮ Non-prinicipalité du cylindre des langages à compteur ⋮ Le cylindre des langages linéaires ⋮ Extensions to Barrington's M-program model ⋮ Hypertree decompositions and tractable queries ⋮ The Hardest Language for Conjunctive Grammars ⋮ Leaf languages and string compression ⋮ Reversal-bounded multipushdown machines ⋮ On characterisation of language families in terms of inverse morphisms ⋮ The descriptive complexity approach to LOGCFL ⋮ Translational lemmas, polynomial time, and \((\log n)^j\)-space ⋮ The computational power of parsing expression grammars ⋮ On hardest languages for one-dimensional cellular automata ⋮ A representation theorem of infinite dimensional algebras and applications to language theory ⋮ Associative language descriptions ⋮ Computing LOGCFL certificates ⋮ A note on classes of complements and the LBA-problem ⋮ On inverse deterministic pushdown transductions ⋮ Classes of formal grammars ⋮ Opérations de cylindre et applications séquentielles gauches inverses ⋮ Générateurs algébriques et systèmes de paires iterantes ⋮ On simple generators of recursively enumerable languages ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ From decidability to undecidability by considering regular sets of instances ⋮ Languages recognized by finite aperiodic groupoids ⋮ Finite transducers and rational transductions ⋮ Langages à un compteur ⋮ A note on context free languages, complexity classes, and diagonalization ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ Remarks on multihead pushdown automata and multihead stack automata ⋮ An inverse homomorphic characterization of full principal AFL ⋮ Alternating multicounter machines with constant number of reversals
