Expressive power of LL(k) Boolean grammars
Boolean grammars [the author, ``Boolean grammars, Inf. Comput. 194, No. 1, 19--48 (2004; Zbl 1073.68037)] extend the definition of context-free grammars by allowing explicit Boolean operations in the rules in the sense that standard context-free grammars can combine syntactical conditions using disjunction (effectively specified by multiple rules for a single symbol), conjunctive grammars [the author, ``Conjunctive grammars, J. Autom. Lang. Comb. 6, No. 4, 519--535 (2001; Zbl 1004.68082)] additionally allow conjunction, and Boolean grammars further support negation. The paper establishes some limitations of the expressive power of \(\text{LL}(k)\) Boolean grammars, the subcase of Boolean grammars to which recursive descent parsing is applicable [the author, ``Recursive descent parsing for Boolean grammars, Acta Inf. 44, No. 3--4, 167--189 (2007; Zbl 1119.68101)]. After the definition of Boolean grammars, recursive descent parsers for Boolean grammars, and the presentation of some simple normal forms, it is proved that Boolean LL grammars over a unary alphabet generate only regular languages. This is in contrast with general conjunctive grammars which are known to have greater expressive power over one letter alphabets. This result is then used to demonstrate that languages of the form \(\{a^n b^{f(n)} \mid n\geq 1\}\) can only be generated by Boolean LL grammars if \(f(n)\) is linearly bounded (this implies the non-representability of the language \(\{a^nb^{2^n} \mid n\geq 0\}\)). Next, stronger non-representability results are obtained for linear conjunctive LL grammars and linear Boolean LL grammars, then based on these a detailed hierarchy of language families is obtained. Finally, closure properties of these families are determined and compared to the known closure properties of context-free LL languages.
- Expressive Power of LL(k) Boolean Grammars
- Boolean grammars
- Unambiguous Boolean grammars
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- Well-Founded Semantics for Boolean Grammars
- The Boolean closure of linear context-free languages
- Recursive descent parsing for Boolean grammars
- Developments in Language Theory
- Well-founded semantics for Boolean grammars
- Mathematical Foundations of Computer Science 2005
- A further note on top-down deterministic languages
- A property of real-time trellis automata
- A simple P-complete problem and its language-theoretic representations
- Boolean grammars
- Characterizations and computational complexity of systolic trellis automata
- Closure properties of cellular automata
- Comparing linear conjunctive languages to subfamilies of the context-free languages
- Complexity of equations over sets of natural numbers
- CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
- Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
- Conjunctive grammars with restricted disjunction
- Expressive Power of LL(k) Boolean Grammars
- Fast parsing for Boolean grammars: a generalization of Valiant's algorithm
- GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 1747449 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- Language Equations with Symmetric Difference
- Lower bound technique for length-reducing automata
- Notes on dual concatenation
- On real time one-way cellular array
- On the closure properties of linear conjunctive languages.
- On the equivalence of linear conjunctive grammars and trellis automata
- One-nonterminal conjunctive grammars over a unary alphabet
- Properties of deterministic top-down grammars
- Recursive descent parsing for Boolean grammars
- Well-founded semantics for Boolean grammars
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- On the Transformation of LL(k)-linear Grammars to LL(1)-linear
- Expressive Power of LL(k) Boolean Grammars
- On the transformation of LL(k)-linear to LL(1)-linear grammars
- \(\mathrm{LL}(k)\) cooperating distributed grammar systems
This page was built for publication: Expressive power of \(\text{LL}(k)\) Boolean grammars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q719251)
