Relations Between Time and Tape Complexities

DOI10.1145/321466.321474MaRDI QIDQ5556431zbMATH OpenOpenAlexFDO

Authors John Hopcroft, Jeffrey D. Ullman

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

Cited in

(16)

• On the structure of one-tape nondeterministic Turing machine time hierarchy
• Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
• Relativized alternation and space-bounded computation
• 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
• A time lower bound for satisfiability
• On time versus space III
• Space-bounded simulation of multitape turing machines
• The theory of languages
• The theory of languages
• On restricted turing computability
• Consistent ultrafinitist logic
• Simulating time with square-root space

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

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