Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
From MaRDI portal
Publication:1113670
DOI10.1016/0022-0000(88)90047-5zbMath0661.68041OpenAlexW2985036451MaRDI QIDQ1113670
Publication date: 1988
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(88)90047-5
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (3)
Queue Automata: Foundations and Developments ⋮ On the power of several queues ⋮ Not all planar digraphs have small cycle separators
Cites Work
- An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
- Tape versus queue and stacks: The lower bounds
- Real time computation
- Time- and tape-bounded Turing acceptors and AFLs
- On-line simulation of k + 1 tapes by k tapes requires nonlinear time
- Limitations on Explicit Constructions of Expanding Graphs
- Two Tapes are Better than One for Nondeterministic Machines
- Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- On the Computational Complexity of Algorithms
- Two-Tape Simulation of Multitape Turing Machines
- One-way stack automata
- Quasi-realtime languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
