Hardest languages for conjunctive and Boolean grammars

DOI10.1016/J.IC.2018.11.001zbMATH Open1426.68152OpenAlexW2905324368MaRDI QIDQ1740643FDOQ1740643

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

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

zbMATH Keywords

conjunctive grammarBoolean grammarhardest language

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

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

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)