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

DOI10.1016/0304-3975(93)90194-XzbMath0783.68054OpenAlexW2073510698MaRDI QIDQ1208717

Wolfgang Maass, Martin Dietzfelbinger

Publication date: 16 May 1993

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

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90194-x

zbMATH Keywords

Turing machinesKolmogorov complexityBoolean matricesoptimal lower boundmatrix transposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

The complexity of matrix transposition on one-tape off-line Turing machines ⋮ Two tapes versus one for off-line Turing machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of matrix transposition on one-tape off-line Turing machines
• Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
• Tape versus queue and stacks: The lower bounds
• Zur Komplexität von Sortierproblemen
• The speed of copying on one-tape off-line turing machines
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• One-tape, off-line Turing machine computations

This page was built for publication: The complexity of matrix transposition on one-tape off-line Turing machines with output tape