The complexity of matrix transposition on one-tape off-line Turing machines with output tape
type: Item
instance of: scholarly article
title: The complexity of matrix transposition on one-tape off-line Turing machines with output tape
zbMATH Open document ID: 0783.68054
DOI: 10.1016/0304-3975(93)90194-X
author: Martin Dietzfelbinger
author: Wolfgang Maass
published in: Theoretical Computer Science
publication date: 1993-05-16T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 166965
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: matrix transposition
zbMATH Keywords: Boolean matrices
zbMATH Keywords: Turing machines
zbMATH Keywords: optimal lower bound
MaRDI profile type: Publication
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
cites work: One-tape, off-line Turing machine computations
cites work: Q5592246
cites work: Q3751011
cites work: Tape versus queue and stacks: The lower bounds
cites work: Q4385509
cites work: Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
cites work: Q3751009
cites work: On-line simulation of k + 1 tapes by k tapes requires nonlinear time
cites work: Zur Komplexität von Sortierproblemen
cites work: Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
full work available at URL: 0304-3975(93)90194-x
OpenAlex ID: W2073510698
description: scientific article; zbMATH DE number 166965