A speed-up theorem without tape compression

DOI10.1016/0304-3975(93)90362-WzbMATH Open0796.68087MaRDI QIDQ688718FDOQ688718

Authors: Viliam Geffert 

Publication date: 6 December 1993

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

Recommendations

• scientific article
• Speed-Up Theorems in Type-2 Computation
• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• The speed of copying on one-tape off-line turing machines
• A note on superlinear speedup
• A theory of incremental compression
• Speed-up theorems in type-2 computations using oracle Turing machines
• An optimal speedup algorithm for the measure problem
• On superlinear speedups
• A new formula for speedup and its characterization

zbMATH Keywords

nondeterminismspeed-upsingle tape Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cites Work

• On the Computational Complexity of Algorithms
• 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>
• Title not available (Why is that?)

Cited In (10)

• Linear speed-up does not hold on Turing machines with tree storages
• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• Complexity of nondeterministic multitape computations based on crossing sequences
• Fast probabilistic RAM simulation of single tape turing machine computations
• Speed-Up Theorems in Type-2 Computation
• Complement for two-way alternating automata
• Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space
• On the structure of one-tape nondeterministic Turing machine time hierarchy
• Alternating space is closed under complement and other simulations for sublogarithmic space
• Title not available (Why is that?)

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

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