A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages

DOI10.1145/321906.321913zbMath0318.68048OpenAlexW2090004024MaRDI QIDQ4080742

Ivan Hal Sudborough

Publication date: 1975

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321906.321913

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (32)

On the closure properties of linear conjunctive languages. ⋮ Boolean grammars ⋮ Unnamed Item ⋮ On a complexity hierarchy between L and NL ⋮ Unnamed Item ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ A simple P-complete problem and its language-theoretic representations ⋮ On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata ⋮ A recognition and parsing algorithm for arbitrary conjunctive grammars. ⋮ Tree-size bounded alternation ⋮ Classifying the computational complexity of problems ⋮ Linear-space recognition for grammars with contexts ⋮ Time complexity of languages recognized by one-way multihead pushdown automata ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Extending regular expressions with homomorphic replacement ⋮ Le cylindre des langages linéaires ⋮ Extensions to Barrington's M-program model ⋮ Unambiguity of circuits ⋮ On partially blind multihead finite automata. ⋮ On state-alternating context-free grammars ⋮ The LBA-problem and the deterministic tape complexity of two-way one- counter languages over a one-letter alphabet ⋮ Formal languages over GF(2) ⋮ One way finite visit automata ⋮ Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ On The Space Complexity Of Turn Bounded Pushdown Automata ⋮ Complexity of some problems concerningL systems ⋮ Some classes of languages in \(NC^ 1\) ⋮ On Computational Power of Partially Blind Automata ⋮ Two-sided context specifications in formal grammars ⋮ Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines

This page was built for publication: A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages