On-line simulation of k + 1 tapes by k tapes requires nonlinear time
From MaRDI portal
Publication:3321474
DOI10.1016/S0019-9958(82)91055-5zbMath0536.68049OpenAlexW2034943218MaRDI QIDQ3321474
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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
