Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth

DOI10.1007/978-3-540-74510-5_19MaRDI QIDQ3499774zbMATH OpenOpenAlexFDO

Authors Artur Jeż, Alexander Okhotin

Publication date 3 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74510-5_19

Mathematics Subject Classification ID

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

Recommendations

• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Unambiguous conjunctive grammars over a one-letter alphabet
• Unambiguous conjunctive grammars over a one-symbol alphabet
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Conjunctive Grammars Can Generate Non-regular Unary Languages

Cited in

(13)

• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• One-Nonterminal Conjunctive Grammars over a Unary Alphabet
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Conjunctive Grammars with Restricted Disjunction
• A Game-Theoretic Characterization of Boolean Grammars
• On Equations over Sets of Numbers and Their Limitations
• Unambiguous conjunctive grammars over a one-symbol alphabet
• Unambiguous conjunctive grammars over a one-letter alphabet
• Conjunctive Grammars Can Generate Non-regular Unary Languages
• A game-theoretic characterization of Boolean grammars
• One-nonterminal conjunctive grammars over a unary alphabet
• Conjunctive grammars, cellular automata and logic
• Locally stratified Boolean grammars

This page was built for publication: Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3499774)