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

DOI10.1137/0219034zbMath0698.68057OpenAlexW2049688961MaRDI 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

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)

Related Items (2)

A speed-up theorem without tape compression ⋮ Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences

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