The complexity of matrix transposition on one-tape off-line Turing machines
type: Item
instance of: scholarly article
title: The complexity of matrix transposition on one-tape off-line Turing machines
zbMATH Open document ID: 0731.68042
DOI: 10.1016/0304-3975(91)90175-2
author: Martin Dietzfelbinger
author: Wolfgang Maass
author: Georg Schnitger
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4209591
zbMATH Keywords: lower bound
zbMATH Keywords: one-tap off-line Turing machines
MaRDI profile type: Publication
full work available at URL: 0304-3975(91)90175-2
OpenAlex ID: W1972152334
cites work: 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
cites work: Q5759552
cites work: One-tape, off-line Turing machine computations
cites work: Q5592246
cites work: On Time Versus Space
cites work: Q3751011
cites work: Q3033321
cites work: Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
cites work: Q3751009
cites work: Q4766586
cites work: Q3051378
cites work: On-line simulation of k + 1 tapes by k tapes requires nonlinear time
cites work: Rangierkomplexität von Permutationen
Recommended article: The complexity of matrix transposition on one-tape off-line Turing machines with output tape
Recommended article: Q3795216
Recommended article: Q5192993
Recommended article: Q3706503
Recommended article: Transposition of an \(\ell \times \ell\) matrix requires \(\Omega\) (log \(\ell)\) reversals on conservative Turing machines
Recommended article: Q4820785
Recommended article: On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals
Recommended article: Q4016519
Recommended article: On the Limits of Cache-Oblivious Matrix Transposition
Recommended article: The speed of copying on one-tape off-line turing machines
description: scientific article; zbMATH DE number 4209591