A speed-up theorem without tape compression

DOI10.1016/0304-3975(93)90362-WzbMath0796.68087MaRDI QIDQ688718

Viliam Geffert

Publication date: 6 December 1993

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

zbMATH Keywords

nondeterminismspeed-upsingle tape Turing machines

Mathematics Subject Classification ID

Related Items (3)

Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ Complement for two-way alternating automata ⋮ Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space

Cites Work

• Unnamed Item
• Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
• Some Time-Space Tradeoff Results Concerning Single-Tape and Offline TM’<scp>s</scp>
• On the Computational Complexity of Algorithms

This page was built for publication: A speed-up theorem without tape compression