CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
From MaRDI portal
Publication:3538852
DOI10.1142/S012905410800584XzbMath1155.68040MaRDI 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
Linear grammars with one-sided contexts and their automaton representation, Formal languages over GF(2), Least and greatest solutions of equations over sets of integers, Equations over sets of integers with addition only, 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, Unambiguous conjunctive grammars over a one-symbol alphabet, Complexity of equations over sets of natural numbers, One-nonterminal conjunctive grammars over a unary alphabet, Representing hyper-arithmetical sets by equations over sets of integers, Parsing Boolean grammars over a one-letter alphabet using online convolution, Expressive power of \(\text{LL}(k)\) Boolean grammars, Language equations with complementation: expressive power, Unambiguous Boolean grammars, Conjunctive grammars with restricted disjunction, Language equations, Computational completeness of equations over sets of natural numbers, An extension of context-free grammars with one-sided context specifications, Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth, Two-sided context specifications in formal grammars, Conjunctive grammars and alternating pushdown automata, Input-driven languages are linear conjunctive, BOOLEAN GRAMMARS AND GSM MAPPINGS, Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages, One-Nonterminal Conjunctive Grammars over a Unary Alphabet, Conjunctive Grammars with Restricted Disjunction
Cites Work