A tradeoff theorem for space and reversal

DOI10.1016/0304-3975(84)90033-1zbMATH Open0545.68037OpenAlexW1983275069MaRDI QIDQ797282FDOQ797282

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)

Cites Work

• Title not available (Why is that?)
• Storage Modification Machines

Cited In (5)

• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• Sublogarithmic Bounds on Space and Reversals
• Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space
• Complexity theory of parallel time and hardware
• Alternating space is closed under complement and other simulations for sublogarithmic space

   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 👍 👎

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)