Tape versus queue and stacks: The lower bounds
From MaRDI portal
Publication:1109567
DOI10.1016/0890-5401(88)90003-XzbMath0655.68046MaRDI QIDQ1109567
Publication date: 1988
Published in: Information and Computation (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (10)
Fast nondeterministic recognition of context-free languages using two queues ⋮ 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 ⋮ Queue Automata: Foundations and Developments ⋮ 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 ⋮ The speed of copying on one-tape off-line turing machines ⋮ Three one-way heads cannot do string matching ⋮ Two tapes versus one for off-line Turing machines
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
- An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
- An information-theoretic approach to time bounds for on-line computation
- On the simulation of many storage heads by one
- Real time computation
- On-line simulation of k + 1 tapes by k tapes requires nonlinear time
- Two Tapes are Better than One for Nondeterministic Machines
- Two nonlinear lower bounds for on-line computations
- Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
- Algorithmic Information Theory
- On the Computational Complexity of Algorithms
- Two-Tape Simulation of Multitape Turing Machines
- On the Length of Programs for Computing Finite Binary Sequences
- A formal theory of inductive inference. Part I
This page was built for publication: Tape versus queue and stacks: The lower bounds
