Real-Time Simulation of Multihead Tape Units

DOI10.1145/321724.321726zbMath0261.68027OpenAlexW2051177275MaRDI QIDQ5677074

Albert R. Meyer, Patrick C. Fischer, Arnold L. Rosenberg

Publication date: 1972

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (22)

Invariance properties of RAMs and linear time ⋮ Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract) ⋮ Relativized alternation and space-bounded computation ⋮ A Turing machine time hierarchy ⋮ Data encodings and their costs ⋮ Indirect addressing and the time relationships of some models of sequential computation ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ A simplified proof of the real-time recognizability of palindromes on Turing machines ⋮ Complexity of algorithms and computations ⋮ An information-theoretic approach to time bounds for on-line computation ⋮ Real-time recognition of substring repetition and reversal ⋮ Iterative arrays with direct central control ⋮ On the sequential nature of functions ⋮ Three write heads are as good ask ⋮ Palindrome recognition in real time by a multitape Turing machine ⋮ Real-time computations with restricted nondeterminism ⋮ Reductions and functors from problems to word problems ⋮ Linear-time simulation of multihead Turing machines ⋮ Relative complexity of operations on numeric and bit-string algebras ⋮ On heads versus tapes ⋮ On two-tape real-time computation and queues ⋮ Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit

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