Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages

DOI10.1007/978-3-642-18381-2_36zbMath1298.68153OpenAlexW1486955936MaRDI QIDQ3075534

Alexander Okhotin

Publication date: 15 February 2011

Published in: SOFSEM 2011: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-18381-2_36

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Related Items (7)

Descriptional Complexity of Input-Driven Pushdown Automata ⋮ Recognition of poly-slender context-free languages by trellis automata ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Shrinking one-way cellular automata ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ Toward a theory of input-driven locally parsable languages

Cites Work

• Unnamed Item
• Unnamed Item
• On real time one-way cellular array
• Characterizations and computational complexity of systolic trellis automata
• Unambiguous Boolean grammars
• Conjunctive grammars with restricted disjunction
• Boolean grammars
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Visibly pushdown languages
• Fast Parsing for Boolean Grammars: A Generalization of Valiant’s Algorithm
• A Game-Theoretic Characterization of Boolean Grammars
• Systolic trellis automatat†
• One-way bounded cellular automata
• On the equivalence of linear conjunctive grammars and trellis automata
• Parenthesis Grammars

This page was built for publication: Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages