The speed of copying on one-tape off-line turing machines

DOI10.1016/0020-0190(89)90160-9zbMath0682.68043OpenAlexW2005330446MaRDI QIDQ1824387

Martin Dietzfelbinger

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90160-9

zbMATH Keywords

computational complexitysimulationTuring machinesKolmogorov complexitylower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (4)

On the power of several queues ⋮ The complexity of matrix transposition on one-tape off-line Turing machines with output tape ⋮ The complexity of matrix transposition on one-tape off-line Turing machines ⋮ Two tapes versus one for off-line Turing machines

Cites Work

• The complexity of matrix transposition on one-tape off-line Turing machines
• Tape versus queue and stacks: The lower bounds
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• One-tape, off-line Turing machine computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The speed of copying on one-tape off-line turing machines