Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
From MaRDI portal
Publication:2268341
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
- scientific article; zbMATH DE number 5605108 (Why is no real title available?)
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- scientific article; zbMATH DE number 1747449 (Why is no real title available?)
- scientific article; zbMATH DE number 3302285 (Why is no real title available?)
- CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
- Characterizations and computational complexity of systolic trellis automata
- Conjunctive grammars and systems of language equations
- Finite automata and unary languages
- Language Equations with Complementation
- On the equivalence of linear conjunctive grammars and trellis automata
- Simulating finite automata with context-free grammars.
- Systolic trellis automata: Stability, decidability and complexity
- Systolic trellis automatata †
- Systolic trellis automatat†
- Two Families of Languages Related to ALGOL
- Unrestricted complementation in language equations over a one-letter alphabet
Cited in
(30)- Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
- Boolean grammars and gsm mappings
- Input-driven languages are linear conjunctive
- Conjunctive grammars and alternating pushdown automata
- Comparing linear conjunctive languages to subfamilies of the context-free languages
- Conjunctive grammars with restricted disjunction
- Language equations with complementation: expressive power
- Formal languages over GF(2)
- Complexity of equations over sets of natural numbers
- On the expressive power of univariate equations over sets of natural numbers
- Language equations
- Expressive power of \(\text{LL}(k)\) Boolean grammars
- Computational completeness of equations over sets of natural numbers
- CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
- Parsing by matrix multiplication generalized to Boolean grammars
- Unambiguous conjunctive grammars over a one-letter alphabet
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- A simple P-complete problem and its language-theoretic representations
- On equations over sets of numbers and their limitations
- Conjunctive Grammars Can Generate Non-regular Unary Languages
- Linear grammars with one-sided contexts and their automaton representation
- Representing hyper-arithmetical sets by equations over sets of integers
- One-Nonterminal Conjunctive Grammars over a Unary Alphabet
- One-nonterminal conjunctive grammars over a unary alphabet
- Unambiguous conjunctive grammars over a one-symbol alphabet
- Parsing Boolean grammars over a one-letter alphabet using online convolution
- Equations over sets of integers with addition only
- An extension of context-free grammars with one-sided context specifications
- Least and greatest solutions of equations over sets of integers
- Conjunctive grammars, cellular automata and logic
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)
