Some Time-Space Tradeoff Results Concerning Single-Tape and Offline TM’<scp>s</scp>

DOI10.1137/0212025MaRDI QIDQ3657434zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, Shlomo Moran

Publication date 1983

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0212025

zbMATH Keywords

offline Turing machinesingle-tape Turing machinetime-space tradeoff

Mathematics Subject Classification ID

Cited in

(4)

• On the structure of one-tape nondeterministic Turing machine time hierarchy
• Complexity of nondeterministic multitape computations based on crossing sequences
• A speed-up theorem without tape compression
• Simulating time with square-root space

This page was built for publication: Some Time-Space Tradeoff Results Concerning Single-Tape and Offline TM’<scp>s</scp>

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