Real-Time Simulation of Multihead Tape Units
From MaRDI portal
Cited in
(22)- Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
- Relativized alternation and space-bounded computation
- Data encodings and their costs
- Indirect addressing and the time relationships of some models of sequential computation
- 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
- Iterative arrays with direct central control
- On the sequential nature of functions
- Palindrome recognition in real time by a multitape Turing machine
- Invariance properties of RAMs and linear time
- Reductions and functors from problems to word problems
- Linear-time simulation of multihead Turing machines
- Uniform simulations of nondeterministic real time multitape turing machines
- Three write heads are as good ask
- Relative complexity of operations on numeric and bit-string algebras
- Real-time recognition of substring repetition and reversal
- Real-time computations with restricted nondeterminism
- Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract)
- A Turing machine time hierarchy
- On heads versus tapes
- On two-tape real-time computation and queues
This page was built for publication: Real-Time Simulation of Multihead Tape Units
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5677074)
