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

DOI10.1016/J.TCS.2010.09.015zbMATH Open1207.68197OpenAlexW1977695731MaRDI QIDQ616494FDOQ616494

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

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^∗

zbMATH Keywords

language equationsBoolean grammarsconjunctive grammarscircuit value problemTrellis automata

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

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

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)