Relations Between Time and Tape Complexities

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

zbMATH Keywords

recursion theory, constructive mathematics

Related Items (14)

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

This page was built for publication: Relations Between Time and Tape Complexities