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

DOI10.1145/321906.321913MaRDI QIDQ4080742zbMATH OpenOpenAlexFDO

Authors 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

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

Cited in

(32)

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

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)