An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
From MaRDI portal
Publication:1068538
DOI10.1016/0020-0190(85)90020-1zbMath0582.68019OpenAlexW2023886101MaRDI QIDQ1068538
Publication date: 1985
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(85)90020-1
Kolmogorov complexitytime complexitymultitape Turing machineson-line simulation by single- head tape units
Related Items
Tape versus queue and stacks: The lower bounds, Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time, Tradeoffs for language recognition on alternating machines
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On heads versus tapes
- Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
- An information-theoretic approach to time bounds for on-line computation
- On the simulation of many storage heads by one
- Real time computation
- On the complexity of the identity problem for finitely defined groups
- On-line simulation of k + 1 tapes by k tapes requires nonlinear time
- New Real-Time Simulations of Multihead Tape Units
- Algorithmic Information Theory
