A Note Concerning Nondeterministic Tape Complexities
From MaRDI portal
Publication:5658032
DOI10.1145/321724.321727zbMath0245.94044OpenAlexW2060975544MaRDI QIDQ5658032
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
Related Items (16)
On the computational complexity of membrane systems ⋮ A hierarchy for nondeterministic time complexity ⋮ Generalizations of Checking Stack Automata: Characterizations and Hierarchies ⋮ Space hierarchy theorem revised. ⋮ Complexity of algorithms and computations ⋮ Classifying the computational complexity of problems ⋮ Symmetric space-bounded computation ⋮ Interactive proof systems and alternating time-space complexity ⋮ On the complexity of finite, pushdown, and stack automata ⋮ Towards separating nondeterminism from determinism ⋮ Translational lemmas, polynomial time, and \((\log n)^j\)-space ⋮ Comparing complexity classes ⋮ On the equivalence, containment, and covering problems for the regular and context-free languages ⋮ Techniques for separating space complexity classes ⋮ Relating refined space complexity classes ⋮ On two-way multihead automata
This page was built for publication: A Note Concerning Nondeterministic Tape Complexities
