On the number of nonterminals in linear conjunctive grammars
From MaRDI portal
Publication:596108
DOI10.1016/j.tcs.2004.03.002zbMath1068.68072MaRDI QIDQ596108
Publication date: 10 August 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.03.002
automaton; Cellular; Conjunctive grammar; Descriptional complexity; Formal languages; Language equation; Minimal linear grammar; Trellis automaton
Related Items
Cites Work
- On real time one-way cellular array
- On real-time cellular automata and trellis automata
- Characterizations and computational complexity of systolic trellis automata
- The hardest linear conjunctive language
- Nonterminal complexity of programmed grammars.
- A recognition and parsing algorithm for arbitrary conjunctive grammars.
- Conjunctive grammars and systems of language equations
- On the closure properties of linear conjunctive languages.
- Real-time language recognition by one-dimensional cellular automata
- Systolic trellis automata: Stability, decidability and complexity
- Systolic trellis automatat†
- Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
- One-way bounded cellular automata
- On the Succinctness of Different Representations of Languages
- On the equivalence of linear conjunctive grammars and trellis automata
- The undecidability of the ambiguity problem for minimal linear grammars
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item