The Hardest Context-Free Language

Cited in

(63)

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
On morphic generation of regular languages
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)
Parallel complexity of logical query programs
Some subclasses of context-free languages in NC^ 1
Langages sur des alphabets infinis
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
Nonuniform complexity and the randomness of certain complete languages
Complexity in left-associative grammar
Extensions to Barrington's M-program model
Reversal-bounded multipushdown machines
Translational lemmas, polynomial time, and \((\log n)^j\)-space
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
Languages recognized by finite aperiodic groupoids
Restrictions and representations of vector controlled concurrent system behaviours
McNaughton families of languages.
Knapsack in graph groups
Hardest languages for conjunctive and Boolean grammars
Langages à un compteur
From decidability to undecidability by considering regular sets of instances
Finite transducers and rational transductions
On hardest languages for one-dimensional cellular automata
Self-reducibility
On characterisation of language families in terms of inverse morphisms
On Second-Order Monadic Groupoidal Quantifiers
scientific article; zbMATH DE number 3673546 (Why is no real title available?)
scientific article; zbMATH DE number 3677223 (Why is no real title available?)
A note on context free languages, complexity classes, and diagonalization
Conjunctive and Boolean grammars: the true general case of the context-free grammars
Sur la structure des langages algébriques
On the complexity of finite, pushdown, and stack automata
Non-prinicipalité du cylindre des langages à compteur
Le cylindre des langages linéaires
scientific article; zbMATH DE number 3576701 (Why is no real title available?)
The complexity of the membership problem for some extensions of context-free languagest†
Leaf languages and string compression
Uniform Constraint Satisfaction Problems and Database Theory
The hardest language for conjunctive grammars
A representation theorem of infinite dimensional algebras and applications to language theory
The descriptive complexity approach to LOGCFL
Associative language descriptions
Computing LOGCFL certificates
The hardest language for grammars with context operators
The Hardest LL(k) Language
On hardest languages for one-dimensional cellular automata
On the complexity of regular-grammars with integer attributes
Reachability in fixed VASS: expressiveness and lower bounds
On the expressive power of categorial grammars with unique category assignment
Hypertree decompositions and tractable queries
On simple generators of recursively enumerable languages
The hardest \(\operatorname{LL}(k)\) language
Weighted hypertree decompositions and optimal query plans

This page was built for publication: The Hardest Context-Free Language

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4404463)