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

DOI10.1016/0304-3975(91)90175-2zbMATH Open0731.68042OpenAlexW1972152334MaRDI QIDQ808247FDOQ808247

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

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

zbMATH Keywords

lower boundone-tap off-line Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On Time Versus Space
• One-tape, off-line Turing machine computations
• 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
• The complexity of matrix transposition on one-tape off-line Turing machines with output tape
• Rangierkomplexität von Permutationen
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (7)

• New lower bounds for element distinctness on a one-tape Turing machine
• The speed of copying on one-tape off-line turing machines
• Sorting and Element Distinctness on One-Way Turing Machines
• Title not available (Why is that?)
• 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
• The complexity of matrix transposition on one-tape off-line Turing machines with output tape

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)