On-line simulation of k + 1 tapes by k tapes requires nonlinear time

DOI10.1016/S0019-9958(82)91055-5zbMath0536.68049OpenAlexW2034943218MaRDI QIDQ3321474

Wolfgang J. Paul

Publication date: 1982

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(82)91055-5

zbMATH Keywords

on-line simulationreal-time Turing machine

Mathematics Subject Classification ID

Related Items (18)

On the structure of one-tape nondeterministic Turing machine time hierarchy ⋮ On the simulation of many storage heads by one ⋮ Hierarchies of one-way multihead automata languages ⋮ Remarks on string-matching and one-way multihead automata ⋮ Tape versus queue and stacks: The lower bounds ⋮ k\(+1\) heads are better than k for PDAs ⋮ Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time ⋮ Deterministic realization of nondeterministic computations with a low measure of nondeterminism ⋮ Limitations of the upward separation technique ⋮ Downward translations of equality ⋮ Milking the Aanderaa argument ⋮ On the power of several queues ⋮ \(k\) versus \(k+1\) index registers and modifiable versus non-modifiable programs ⋮ The complexity of matrix transposition on one-tape off-line Turing machines with output tape ⋮ Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines ⋮ On two-tape real-time computation and queues ⋮ The complexity of matrix transposition on one-tape off-line Turing machines ⋮ An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape

This page was built for publication: On-line simulation of k + 1 tapes by k tapes requires nonlinear time