A Note Concerning Nondeterministic Tape Complexities

DOI10.1145/321724.321727MaRDI QIDQ5658032zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra

Publication date 1972

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Turing machines and related notions (03D10)

Cited in

(16)

• On the computational complexity of membrane systems
• Towards separating nondeterminism from determinism
• Relating refined space complexity classes
• Techniques for separating space complexity classes
• Translational lemmas, polynomial time, and \((\log n)^j\)-space
• A hierarchy for nondeterministic time complexity
• Classifying the computational complexity of problems
• Comparing complexity classes
• On the complexity of finite, pushdown, and stack automata
• Interactive proof systems and alternating time-space complexity
• Complexity of algorithms and computations
• On the equivalence, containment, and covering problems for the regular and context-free languages
• Generalizations of Checking Stack Automata: Characterizations and Hierarchies
• On two-way multihead automata
• Symmetric space-bounded computation
• Space hierarchy theorem revised.

This page was built for publication: A Note Concerning Nondeterministic Tape Complexities

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