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

DOI10.1016/0304-3975(91)90175-2MaRDI QIDQ808247zbMATH OpenOpenAlexFDO

Authors Martin Dietzfelbinger, Wolfgang Maass, 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)

Recommendations

• The complexity of matrix transposition on one-tape off-line Turing machines with output tape
• scientific article; zbMATH DE number 4060710
• scientific article; zbMATH DE number 5593330
• scientific article; zbMATH DE number 3934409
• Transposition of an \(\ell \times \ell\) matrix requires \(\Omega\) (log \(\ell)\) reversals on conservative Turing machines
• scientific article; zbMATH DE number 2104735
• On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals
• scientific article; zbMATH DE number 88942
• On the Limits of Cache-Oblivious Matrix Transposition
• The speed of copying on one-tape off-line turing machines

Cites work

• scientific article; zbMATH DE number 4131660 (Why is no real title available?)
• scientific article; zbMATH DE number 3646282 (Why is no real title available?)
• scientific article; zbMATH DE number 3988711 (Why is no real title available?)
• scientific article; zbMATH DE number 3988713 (Why is no real title available?)
• scientific article; zbMATH DE number 3441617 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• On Time Versus Space
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• One-tape, off-line Turing machine computations
• Rangierkomplexität von Permutationen
• 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

Cited in

(7)

• scientific article; zbMATH DE number 4060710 (Why is no real title available?)
• The complexity of matrix transposition on one-tape off-line Turing machines with output tape
• Element Distinctness and Sorting on One-Tape Off-Line Turing Machines
• Transposition of an \(\ell \times \ell\) matrix requires \(\Omega\) (log \(\ell)\) reversals on conservative Turing machines
• Sorting and Element Distinctness on One-Way Turing Machines
• The speed of copying on one-tape off-line turing machines
• New lower bounds for element distinctness on a one-tape Turing machine

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808247)