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

DOI10.1145/321906.321913zbMATH Open0318.68048OpenAlexW2090004024MaRDI QIDQ4080742FDOQ4080742

I. H. 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

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

Cited In (32)

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

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

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