CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
From MaRDI portal
Publication:3538852
DOI10.1142/S012905410800584XzbMath1155.68040OpenAlexW3145062246MaRDI QIDQ3538852
Publication date: 24 November 2008
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s012905410800584x
Related Items (26)
Equations over sets of integers with addition only ⋮ Conjunctive grammars and alternating pushdown automata ⋮ Input-driven languages are linear conjunctive ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On the expressive power of univariate equations over sets of natural numbers ⋮ Complexity of equations over sets of natural numbers ⋮ One-nonterminal conjunctive grammars over a unary alphabet ⋮ Unambiguous Boolean grammars ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ Computational completeness of equations over sets of natural numbers ⋮ An extension of context-free grammars with one-sided context specifications ⋮ Representing hyper-arithmetical sets by equations over sets of integers ⋮ Conjunctive grammars with restricted disjunction ⋮ Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth ⋮ Parsing Boolean grammars over a one-letter alphabet using online convolution ⋮ Conjunctive Grammars with Restricted Disjunction ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ BOOLEAN GRAMMARS AND GSM MAPPINGS ⋮ Formal languages over GF(2) ⋮ Least and greatest solutions of equations over sets of integers ⋮ Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages ⋮ One-Nonterminal Conjunctive Grammars over a Unary Alphabet ⋮ Language equations with complementation: expressive power ⋮ Language equations ⋮ Linear grammars with one-sided contexts and their automaton representation ⋮ Two-sided context specifications in formal grammars
Cites Work
This page was built for publication: CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
