Expressive power of \(\text{LL}(k)\) Boolean grammars

DOI10.1016/j.tcs.2011.05.013zbMath1239.68040OpenAlexW2038010989MaRDI QIDQ719251

Alexander Okhotin

Publication date: 10 October 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.013

zbMATH Keywords

context-free grammarsparsinglanguage equationsBoolean grammarsconjunctive grammarsLL grammarsrecursive descent

Mathematics Subject Classification ID

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

Related Items (3)

On the Transformation of LL(k)-linear Grammars to LL(1)-linear ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On the transformation of LL\((k)\)-linear to LL(1)-linear grammars

Uses Software

• UCFL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple P-complete problem and its language-theoretic representations
• Complexity of equations over sets of natural numbers
• One-nonterminal conjunctive grammars over a unary alphabet
• On real time one-way cellular array
• Characterizations and computational complexity of systolic trellis automata
• Closure properties of cellular automata
• Well-founded semantics for Boolean grammars
• Conjunctive grammars with restricted disjunction
• A property of real-time trellis automata
• On the closure properties of linear conjunctive languages.
• Boolean grammars
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Lower bound technique for length-reducing automata
• Recursive descent parsing for Boolean grammars
• Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages
• NOTES ON DUAL CONCATENATION
• Language Equations with Symmetric Difference
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Fast Parsing for Boolean Grammars: A Generalization of Valiant’s Algorithm
• On the equivalence of linear conjunctive grammars and trellis automata
• Expressive Power of LL(k) Boolean Grammars
• GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
• Properties of deterministic top-down grammars
• A further note on top-down deterministic languages

This page was built for publication: Expressive power of \(\text{LL}(k)\) Boolean grammars