Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
From MaRDI portal
Publication:2268341
DOI10.1007/S00224-008-9139-5zbMATH Open1183.68327OpenAlexW2154949534MaRDI QIDQ2268341FDOQ2268341
Authors: Artur Jeż, Alexander Okhotin 
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
Recommendations
- Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
- Unambiguous conjunctive grammars over a one-letter alphabet
- One-nonterminal conjunctive grammars over a unary alphabet
- One-Nonterminal Conjunctive Grammars over a Unary Alphabet
- Unambiguous conjunctive grammars over a one-symbol alphabet
- On the number of nonterminal symbols in unambiguous conjunctive grammars
- On the number of nonterminal symbols in unambiguous conjunctive grammars
- An undecidable problem for context-free grammars
- On the size of unambiguous context-free grammars
- On undecidability of concatenation theory for one-symbol languages
Cites Work
- Title not available (Why is that?)
- Unrestricted complementation in language equations over a one-letter alphabet
- CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
- Title not available (Why is that?)
- On the equivalence of linear conjunctive grammars and trellis automata
- Two Families of Languages Related to ALGOL
- Finite automata and unary languages
- Conjunctive grammars and systems of language equations
- Systolic trellis automata: Stability, decidability and complexity
- Title not available (Why is that?)
- Systolic trellis automatata †
- Title not available (Why is that?)
- Characterizations and computational complexity of systolic trellis automata
- Systolic trellis automatat†
- Simulating finite automata with context-free grammars.
- Language Equations with Complementation
Cited In (29)
- On the expressive power of univariate equations over sets of natural numbers
- CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
- Parsing Boolean grammars over a one-letter alphabet using online convolution
- A simple P-complete problem and its language-theoretic representations
- One-nonterminal conjunctive grammars over a unary alphabet
- Expressive power of \(\text{LL}(k)\) Boolean grammars
- Conjunctive grammars with restricted disjunction
- Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
- An extension of context-free grammars with one-sided context specifications
- Boolean grammars and gsm mappings
- Comparing linear conjunctive languages to subfamilies of the context-free languages
- Unambiguous conjunctive grammars over a one-letter alphabet
- Equations over sets of integers with addition only
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- Complexity of equations over sets of natural numbers
- Representing hyper-arithmetical sets by equations over sets of integers
- Language equations with complementation: expressive power
- Conjunctive grammars and alternating pushdown automata
- On equations over sets of numbers and their limitations
- Language equations
- Input-driven languages are linear conjunctive
- One-Nonterminal Conjunctive Grammars over a Unary Alphabet
- Computational completeness of equations over sets of natural numbers
- Formal languages over GF(2)
- Conjunctive Grammars Can Generate Non-regular Unary Languages
- Linear grammars with one-sided contexts and their automaton representation
- Unambiguous conjunctive grammars over a one-symbol alphabet
- Parsing by matrix multiplication generalized to Boolean grammars
- Least and greatest solutions of equations over sets of integers
Uses Software
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 Q2268341)
