Hardest languages for conjunctive and Boolean grammars

DOI10.1016/J.IC.2018.11.001MaRDI QIDQ1740643zbMATH OpenOpenAlexFDO

Authors Alexander Okhotin

Publication date 2 May 2019

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2018.11.001

zbMATH Keywords

conjunctive grammarBoolean grammarhardest language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Recommendations

• The hardest \(\operatorname{LL}(k)\) language
• The hardest language for conjunctive grammars
• The hardest linear conjunctive language
• On characterisation of language families in terms of inverse morphisms
• Conjunctive and Boolean grammars: the true general case of the context-free grammars

Cites work

• scientific article; zbMATH DE number 3673546 (Why is no real title available?)
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 522856 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• A tale of conjunctive grammars
• An extension of context-free grammars with one-sided context specifications
• Boolean grammars
• Boolean grammars and gsm mappings
• Chomsky-Schützenberger-type characterization of multiple context-free languages
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Conjunctive grammars in Greibach normal form and the Lambek calculus with additive connectives
• Conjunctive grammars with restricted disjunction
• Homomorphic Characterizations of Indexed Languages
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata
• Le cylindre des langages linéaires
• Non-erasing Variants of the Chomsky–Schützenberger Theorem
• Non-prinicipalité du cylindre des langages à compteur
• On morphic generation of regular languages
• On multiple context-free grammars
• On real time one-way cellular array
• On the equivalence of linear conjunctive grammars and trellis automata
• Parsing by matrix multiplication generalized to Boolean grammars
• Recognition of poly-slender context-free languages by trellis automata
• Syntactic Analysis and Operator Precedence
• The Hardest Context-Free Language
• The missing case in Chomsky-Schützenberger theorem
• Tree adjunct grammars
• Two-sided context specifications in formal grammars
• Underlying principles and recurring ideas of formal grammars
• Visibly pushdown languages
• Well-founded semantics for Boolean grammars

Cited in

(8)

• The hardest \(\operatorname{LL}(k)\) language
• The hardest linear conjunctive language
• The hardest language for grammars with context operators
• On characterisation of language families in terms of inverse morphisms
• The Hardest LL(k) Language
• On hardest languages for one-dimensional cellular automata
• On hardest languages for one-dimensional cellular automata
• The hardest language for conjunctive grammars

This page was built for publication: Hardest languages for conjunctive and Boolean grammars

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