A simple P-complete problem and its language-theoretic representations
From MaRDI portal
Publication:616494
DOI10.1016/j.tcs.2010.09.015zbMath1207.68197OpenAlexW1977695731MaRDI QIDQ616494
Publication date: 10 January 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.09.015
Related Items (3)
Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Linear-space recognition for grammars with contexts ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the number of nonterminals in linear conjunctive grammars
- On real time one-way cellular array
- Characterizations and computational complexity of systolic trellis automata
- Well-founded semantics for Boolean grammars
- The hardest linear conjunctive language
- Boolean grammars
- Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
- Real-time language recognition by one-dimensional cellular automata
- The dual of concatenation
- Recursive descent parsing for Boolean grammars
- Small Weakly Universal Turing Machines
- Parsing expression grammars
- P-completeness of Cellular Automaton Rule 110
- Systolic trellis automatata †
- Systolic trellis automatat†
- One-way bounded cellular automata
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
- On the equivalence of linear conjunctive grammars and trellis automata
- Expressive Power of LL(k) Boolean Grammars
- GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
- Two Families of Languages Related to ALGOL
This page was built for publication: A simple P-complete problem and its language-theoretic representations
