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

DOI10.1137/0219034zbMATH Open0698.68057OpenAlexW2049688961MaRDI QIDQ3476280FDOQ3476280

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

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

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)

Cited In (26)

• Improved simulation of nondeterministic Turing machines
• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• Title not available (Why is that?)
• Title not available (Why is that?)
• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
• Complexity of nondeterministic multitape computations based on crossing sequences
• Verifying whether one-tape Turing machines run in linear time
• The speed of copying on one-tape off-line 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
• Fast probabilistic RAM simulation of single tape turing machine computations
• Title not available (Why is that?)
• Simulation of three-dimensional one-marker automata by five-way Turing machines
• Improved simulation of nondeterministic Turing machines
• Uniform simulations of nondeterministic real time multitape turing machines
• Title not available (Why is that?)
• On efficient deterministic simulation of turing machine computations below logaspace
• Verifying time complexity of Turing machines
• Mutual upper bounds of size and time for a Turing machine and a Markov-Post algorithm for mutual simulations
• On time versus space III
• A method of analyzing turing computations. II
• Title not available (Why is that?)
• An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits
• On the simulation of many storage heads by one
• Title not available (Why is that?)
• A speed-up theorem without tape compression

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)