A Note Concerning Nondeterministic Tape Complexities

DOI10.1145/321724.321727zbMATH Open0245.94044OpenAlexW2060975544MaRDI QIDQ5658032FDOQ5658032

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