Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones

DOI10.1137/0219034MaRDI QIDQ3476280zbMATH OpenOpenAlexFDO

Authors Maciej Liśkiewicz, Krzysztof Loryś

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0219034

zbMATH Keywords

time-space tradeoffspace-boundedmachines with multidimensional tapeoff-line machinessingle-tape Turing machinetime-bounded

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Recommendations

• scientific article; zbMATH DE number 17549
• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
• scientific article; zbMATH DE number 4078813
• The speed of copying on one-tape off-line turing machines

Cited in

(26)

• On the simulation of many storage heads by one
• Complexity of nondeterministic multitape computations based on crossing sequences
• scientific article; zbMATH DE number 1222596 (Why is no real title available?)
• A method of analyzing turing computations. II
• Verifying time complexity of Turing machines
• scientific article; zbMATH DE number 4060724 (Why is no real title available?)
• scientific article; zbMATH DE number 4049057 (Why is no real title available?)
• Simulation of three-dimensional one-marker automata by five-way Turing machines
• Improved simulation of nondeterministic Turing machines
• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• Mutual upper bounds of size and time for a Turing machine and a Markov-Post algorithm for mutual simulations
• Improved simulation of nondeterministic Turing machines
• The hedge: an efficient storage device for Turing machines with one head
• Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
• scientific article; zbMATH DE number 17549 (Why is no real title available?)
• On time versus space III
• On efficient deterministic simulation of turing machine computations below logaspace
• Verifying whether one-tape Turing machines run in linear time
• A speed-up theorem without tape compression
• Fast probabilistic RAM simulation of single tape turing machine computations
• scientific article; zbMATH DE number 2077107 (Why is no real title available?)
• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
• scientific article; zbMATH DE number 4078813 (Why is no real title available?)
• The speed of copying on one-tape off-line turing machines
• Uniform simulations of nondeterministic real time multitape turing machines
• An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits

This page was built for publication: Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones

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