Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth

DOI10.1007/s00224-008-9139-5zbMath1183.68327OpenAlexW2154949534MaRDI QIDQ2268341

Alexander Okhotin, Artur Jeż

Publication date: 5 March 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-008-9139-5

zbMATH Keywords

cellular automatalanguage equationsunary languagesconjunctive grammarstrellis automata

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Grammars and rewriting systems (68Q42)

Related Items (24)

Equations over sets of integers with addition only ⋮ Conjunctive grammars and alternating pushdown automata ⋮ Input-driven languages are linear conjunctive ⋮ Parsing by matrix multiplication generalized to Boolean grammars ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ A simple P-complete problem and its language-theoretic representations ⋮ 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 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 ⋮ Parsing Boolean grammars over a one-letter alphabet using online convolution ⋮ 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 ⋮ ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS ⋮ Language equations with complementation: expressive power ⋮ Language equations ⋮ Linear grammars with one-sided contexts and their automaton representation

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterizations and computational complexity of systolic trellis automata
• Finite automata and unary languages
• Unrestricted complementation in language equations over a one-letter alphabet
• Conjunctive grammars and systems of language equations
• Simulating finite automata with context-free grammars.
• Systolic trellis automata: Stability, decidability and complexity
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Language Equations with Complementation
• Systolic trellis automatata †
• Systolic trellis automatat†
• On the equivalence of linear conjunctive grammars and trellis automata
• Two Families of Languages Related to ALGOL

This page was built for publication: Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth