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

DOI10.1016/J.TCS.2010.09.015MaRDI QIDQ616494zbMATHOpenAlexFDO

Authors 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)

Recommendations

• A Simple P-Complete Problem and Its Representations by Language Equations
• scientific article; zbMATH DE number 7298596
• The hardest linear conjunctive language
• A syntactical definition of the problem
• The complexity of membership for deterministic growing context-sensitive grammars^∗

Cites work

• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• scientific article; zbMATH DE number 3305022 (Why is no real title available?)
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• Boolean grammars
• Characterizations and computational complexity of systolic trellis automata
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Expressive Power of LL(k) Boolean Grammars
• GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
• On real time one-way cellular array
• On the equivalence of linear conjunctive grammars and trellis automata
• On the number of nonterminals in linear conjunctive grammars
• One-way bounded cellular automata
• P-completeness of Cellular Automaton Rule 110
• Parsing expression grammars: a recognition-based syntactic foundation
• Real-time language recognition by one-dimensional cellular automata
• Recursive descent parsing for Boolean grammars
• Small Weakly Universal Turing Machines
• Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
• Systolic trellis automatata †
• Systolic trellis automatat†
• The dual of concatenation
• The hardest linear conjunctive language
• Two Families of Languages Related to ALGOL
• Universality in elementary cellular automata
• Well-founded semantics for Boolean grammars

Cited in

(9)

• scientific article; zbMATH DE number 7298596 (Why is no real title available?)
• The Boolean formula value problem as formal language
• scientific article; zbMATH DE number 4114061 (Why is no real title available?)
• The hardest linear conjunctive language
• Approximately satisfied properties of systems and simple language homomorphisms
• A Simple P-Complete Problem and Its Representations by Language Equations
• Expressive power of \(\text{LL}(k)\) Boolean grammars
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Linear-space recognition for grammars with contexts

Describes a project that uses

Uses Software

• ALGOL 60

This page was built for publication: A simple P-complete problem and its language-theoretic representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616494)