The complexity of matrix transposition on one-tape off-line Turing machines
From MaRDI portal
Publication:808247
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
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