The Hardest Language for Conjunctive Grammars

DOI10.1007/978-3-319-34171-2_24zbMath1475.68143OpenAlexW2505196311MaRDI QIDQ5740196

Alexander Okhotin

Publication date: 25 July 2016

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-34171-2_24

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Parsing by matrix multiplication generalized to Boolean grammars
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Well-founded semantics for Boolean grammars
• Conjunctive grammars with restricted disjunction
• On multiple context-free grammars
• Conjunctive grammars and systems of language equations
• Boolean grammars
• An extension of context-free grammars with one-sided context specifications
• Two-sided context specifications in formal grammars
• The dual of concatenation
• LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata
• BOOLEAN GRAMMARS AND GSM MAPPINGS
• Non-prinicipalité du cylindre des langages à compteur
• Le cylindre des langages linéaires
• The Hardest Context-Free Language
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars

This page was built for publication: The Hardest Language for Conjunctive Grammars