A tradeoff theorem for space and reversal

DOI10.1016/0304-3975(84)90033-1MaRDI QIDQ797282zbMATH OpenOpenAlexFDO

Authors Jia-Wei Hong

Publication date 1984

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(84)90033-1

zbMATH Keywords

reversalstradeoffoff-line Turing machinework space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines
• A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines
• On the power of 1-tape off-line ATMs running in a bounded number of reversals
• Reversal Complexity
• Time/Space Trade-Offs for Reversible Computation

Cites work

• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Storage Modification Machines

Cited in

(7)

• A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• Alternating demon space is closed under complement and other simulations for sublogarithmic space
• Sublogarithmic Bounds on Space and Reversals
• Complexity theory of parallel time and hardware
• Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines
• Alternating space is closed under complement and other simulations for sublogarithmic space

This page was built for publication: A tradeoff theorem for space and reversal

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