Two tapes versus one for off-line Turing machines
type: Item
instance of: scholarly article
title: Two tapes versus one for off-line Turing machines
zbMATH Open document ID: 0802.68048
DOI: 10.1007/BF01275490
author: Wolfgang Maass
author: Georg Schnitger
author: Gy. Turán
author: Endre Szemerédi
published in: Computational Complexity
publication date: 1994-05-08T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 561486
zbMATH Keywords: lower bounds
zbMATH Keywords: time
zbMATH Keywords: nondeterminism
zbMATH Keywords: off-line 1-tape Turing machine
zbMATH Keywords: two tapes
MaRDI profile type: Publication
cites work: Meanders and their applications in lower bounds arguments
cites work: Lower bounds to the complexity of symmetric Boolean functions
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: One-tape, off-line Turing machine computations
cites work: Q3862379
cites work: Tape versus queue and stacks: The lower bounds
cites work: A Separator Theorem for Planar Graphs
cites work: Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
cites work: Q3751009
cites work: Real time computation
cites work: The performance of multilective VLSI algorithms
full work available at URL: https://doi.org/10.1007/bf01275490
OpenAlex ID: W2079690754
description: scientific article; zbMATH DE number 561486