Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
From MaRDI portal
Publication:3476280
DOI10.1137/0219034zbMath0698.68057MaRDI QIDQ3476280
Krzysztof Loryś, Maciej Liśkiewicz
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
time-space tradeoff; space-bounded; machines with multidimensional tape; off-line machines; single-tape Turing machine; time-bounded
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
03D10: Turing machines and related notions
Related Items
Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences, A speed-up theorem without tape compression