Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
type: Item
instance of: scholarly article
title: Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
zbMATH Open document ID: 0575.68051
DOI: 10.1016/0020-0190(85)90039-0
author: Paul M. B. Vitányi
published in: Information Processing Letters
publication date: 1985-01-01T00:00:00Z
full work available at URL: https://ir.cwi.nl/pub/2523
review text: To simulate a pushdown store or queue on-line by an oblivious one-head tape unit takes at least square time. Since each multitape Turing machine can be trivially simulated by an oblivious one-head tape unit in square time, this result is optimal.
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3919822
zbMATH Keywords: time complexity
zbMATH Keywords: on-line simulation
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: multitape Turing machine
MaRDI profile type: Publication
OpenAlex ID: W1984471632
cites work: Algorithmic Information Theory
cites work: Real-Time Simulation of Multihead Tape Units
cites work: Q5592246
cites work: Q3214803
cites work: Q3933743
description: scientific article; zbMATH DE number 3919822