CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES

DOI10.1142/S012905410800584XzbMath1155.68040OpenAlexW3145062246MaRDI QIDQ3538852

Artur Jeż

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

zbMATH Keywords

context-free grammarslanguage equations

Mathematics Subject Classification ID

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

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

• Conjunctive grammars and systems of language equations
• Boolean grammars

This page was built for publication: CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES