A tradeoff theorem for space and reversal

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

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

• Storage Modification Machines
• Unnamed Item

Related Items (5)

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

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