New Real-Time Simulations of Multihead Tape Units

DOI10.1145/322234.322246MaRDI QIDQ3902483zbMATH OpenOpenAlexFDO

Authors Benton L. Leong, Joel I. Seiferas

Publication date 1981

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/322234.322246

zbMATH Keywords

real-time simulationmultitape Turing machinemultidimensional tapemultihead Turing machine

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25)

Cited in

(13)

• Minimizing access pointers into trees and arrays
• An information-theoretic approach to time bounds for on-line computation
• Linear-time string-matching using only a fixed number of local storage locations
• On computation with pulses
• Dynamical recognizers: real-time language recognition by analog computers
• Simulations among multidimensional Turing machines
• Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract)
• On heads versus tapes
• Deque automata, languages, and planar graph representations
• An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
• Reductions and functors from problems to word problems
• Iterative arrays with direct central control
• On two-tape real-time computation and queues

This page was built for publication: New Real-Time Simulations of Multihead Tape Units

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