The complexity of matrix transposition on one-tape off-line Turing machines

DOI10.1016/0304-3975(91)90175-2zbMath0731.68042OpenAlexW1972152334MaRDI QIDQ808247

Wolfgang Maass, Martin Dietzfelbinger, Georg Schnitger

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90175-2

zbMATH Keywords

lower boundone-tap off-line Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

New lower bounds for element distinctness on a one-tape Turing machine, The complexity of matrix transposition on one-tape off-line Turing machines with output tape, The speed of copying on one-tape off-line turing machines

Cites Work

• The complexity of matrix transposition on one-tape off-line Turing machines with output tape
• The speed of copying on one-tape off-line turing machines
• Rangierkomplexität von Permutationen
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• On Time Versus Space
• One-tape, off-line Turing machine computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item