Tape versus queue and stacks: The lower bounds
From MaRDI portal
Recommendations
Cites work
- A formal theory of inductive inference. Part I
- Algorithmic Information Theory
- 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
- Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
- scientific article; zbMATH DE number 3427210 (Why is no real title available?)
- scientific article; zbMATH DE number 3495593 (Why is no real title available?)
- scientific article; zbMATH DE number 3573787 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- On the Computational Complexity of Algorithms
- On the Length of Programs for Computing Finite Binary Sequences
- On the simulation of many storage heads by one
- On-line simulation of k + 1 tapes by k tapes requires nonlinear time
- Real time computation
- Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
- Two nonlinear lower bounds for on-line computations
- Two Tapes are Better than One for Nondeterministic Machines
- Two-Tape Simulation of Multitape Turing Machines
Cited in
(18)- Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
- 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
- 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
- Three one-way heads cannot do string matching
- Two tapes versus one for off-line Turing machines
- Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
- The speed of copying on one-tape off-line turing machines
- Fast nondeterministic recognition of context-free languages using two queues
- scientific article; zbMATH DE number 3913680 (Why is no real title available?)
- Two nonlinear lower bounds for on-line computations
- The Power of the Queue
- Stacks versus deques
- Queue Automata: Foundations and Developments
- On the power of several queues
- Tradeoff lower lounds for stack machines
- Milking the Aanderaa argument
This page was built for publication: Tape versus queue and stacks: The lower bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109567)