On the simulation of many storage heads by one

DOI10.1016/0304-3975(84)90115-4MaRDI QIDQ1348528zbMATH OpenOpenAlexFDO

Authors Paul M. B. Vitányi

Publication date 13 May 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Turing machines and related notions (03D10)

Recommendations

• Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
• An Optimal Simulation of Counter Machines
• On efficient simulations of multicounter machines
• Milking the Aanderaa argument
• Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones

Cites work

• An information-theoretic approach to time bounds for on-line computation
• An Optimal Simulation of Counter Machines: The ACM Case
• Counter machines and counter languages
• scientific article; zbMATH DE number 3642749 (Why is no real title available?)
• scientific article; zbMATH DE number 3692651 (Why is no real title available?)
• scientific article; zbMATH DE number 3750291 (Why is no real title available?)
• scientific article; zbMATH DE number 3495593 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• On the power of real-time two-way multihead finite automata with jumps
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• Real time computation
• Relations Among Complexity Measures
• Two-Tape Simulation of Multitape Turing Machines

Cited in

(10)

• Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
• An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
• Tape versus queue and stacks: The lower bounds
• The speed of copying on one-tape off-line turing machines
• Linear-time simulation of multihead Turing machines
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• The hedge: an efficient storage device for Turing machines with one head
• An Optimal Simulation of Counter Machines: The ACM Case
• On the power of several queues
• Milking the Aanderaa argument

This page was built for publication: On the simulation of many storage heads by one

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1348528)