Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit

DOI10.1016/0020-0190(85)90039-0zbMath0575.68051OpenAlexW1984471632MaRDI QIDQ1064067

Paul M. B. Vitányi

Publication date: 1985

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/2523

zbMATH Keywords

Kolmogorov complexitytime complexityon-line simulationmultitape Turing machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (5)

The Theta-Model: achieving synchrony without clocks ⋮ Tape versus queue and stacks: The lower bounds ⋮ Tradeoffs for language recognition on alternating machines ⋮ The complexity of matrix transposition on one-tape off-line Turing machines with output tape ⋮ An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic Information Theory
• Real-Time Simulation of Multihead Tape Units

This page was built for publication: Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit