A speed-up theorem without tape compression

DOI10.1016/0304-3975(93)90362-WMaRDI QIDQ688718zbMATHFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 4213433
• 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

Cites work

• scientific article; zbMATH DE number 4078813 (Why is no real title available?)
• Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
• On the Computational Complexity of Algorithms
• Some Time-Space Tradeoff Results Concerning Single-Tape and Offline TM’<scp>s</scp>

Cited in

(10)

• Speed-Up Theorems in Type-2 Computation
• Complexity of nondeterministic multitape computations based on crossing sequences
• On the structure of one-tape nondeterministic Turing machine time hierarchy
• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• Linear speed-up does not hold on Turing machines with tree storages
• Alternating space is closed under complement and other simulations for sublogarithmic space
• Fast probabilistic RAM simulation of single tape turing machine computations
• Alternating demon space is closed under complement and other simulations for sublogarithmic space
• Complement for two-way alternating automata
• scientific article; zbMATH DE number 4078813 (Why is no real title available?)

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)