A simple P-complete problem and its language-theoretic representations
type: Item
instance of: scholarly article
title: A simple P-complete problem and its language-theoretic representations
zbMATH Open document ID: 1207.68197
author: Alexander Okhotin
published in: Theoretical Computer Science
publication date: 2011-01-10T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 5834253
zbMATH Keywords: language equations
zbMATH Keywords: conjunctive grammars
zbMATH Keywords: Boolean grammars
zbMATH Keywords: Trellis automata
zbMATH Keywords: circuit value problem
describes a project that uses: ALGOL 60
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.09.015
OpenAlex ID: W1977695731
cites work: Q5321501
cites work: Systolic trellis automatata †
cites work: Systolic trellis automatat†
cites work: One-way bounded cellular automata
cites work: Parsing expression grammars
cites work: Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
cites work: Two Families of Languages Related to ALGOL
cites work: Q4128417
cites work: Q4843270
cites work: Characterizations and computational complexity of systolic trellis automata
cites work: Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
cites work: Well-founded semantics for Boolean grammars
cites work: Q5586325
cites work: P-completeness of Cellular Automaton Rule 110
cites work: Small Weakly Universal Turing Machines
cites work: Q4531380
cites work: The hardest linear conjunctive language
cites work: On the equivalence of linear conjunctive grammars and trellis automata
cites work: On the number of nonterminals in linear conjunctive grammars
cites work: Boolean grammars
cites work: The dual of concatenation
cites work: GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
cites work: Recursive descent parsing for Boolean grammars
cites work: Expressive Power of LL(k) Boolean Grammars
cites work: Real-time language recognition by one-dimensional cellular automata
cites work: A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
cites work: On real time one-way cellular array
DOI: 10.1016/J.TCS.2010.09.015
description: scientific article; zbMATH DE number 5834253