Relations Between Time and Tape Complexities
From MaRDI portal
Publication:5556431
DOI10.1145/321466.321474zbMath0169.31103OpenAlexW1963576748MaRDI QIDQ5556431
Jeffrey D. Ullman, John E. Hopcrofts
Publication date: 1968
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321466.321474
Related Items
The theory of languages, On the structure of one-tape nondeterministic Turing machine time hierarchy, Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs, The theory of languages, Relativized alternation and space-bounded computation, On time versus space III, On restricted turing computability, On time versus space. II, Complexity of algorithms and computations, Relationships between nondeterministic and deterministic tape complexities, Tape bounds for time-bounded Turing machines, Writing stack acceptors, Space-bounded simulation of multitape turing machines, A time lower bound for satisfiability
