A simple P-complete problem and its language-theoretic representations

DOI10.1016/j.tcs.2010.09.015zbMath1207.68197OpenAlexW1977695731MaRDI QIDQ616494

Alexander Okhotin

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

zbMATH Keywords

language equationsBoolean grammarsconjunctive grammarscircuit value problemTrellis automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

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

• ALGOL 60

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