Simulating two pushdown stores by one tape in O(n^1.5\, \,n) time
DOI10.1016/0022-0000(88)90047-5zbMATH Open0661.68041OpenAlexW2985036451MaRDI QIDQ1113670FDOQ1113670
Authors: Ming Li 
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
Recommendations
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Cites Work
- Applications of a Planar Separator Theorem
- On the Computational Complexity of Algorithms
- A Separator Theorem for Planar Graphs
- Quasi-realtime languages
- Title not available (Why is that?)
- Tape versus queue and stacks: The lower bounds
- Title not available (Why is that?)
- Limitations on Explicit Constructions of Expanding Graphs
- Two-Tape Simulation of Multitape Turing Machines
- One-way stack automata
- Real time computation
- On-line simulation of k + 1 tapes by k tapes requires nonlinear time
- Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
- Title not available (Why is that?)
- Two Tapes are Better than One for Nondeterministic Machines
- An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
- Title not available (Why is that?)
- Time- and tape-bounded Turing acceptors and AFLs
Cited In (13)
- Title not available (Why is that?)
- Milking the Aanderaa argument
- Two Tapes are Better than One for Nondeterministic Machines
- Simulation of two-way pushdown automata revisited
- On the power of several queues
- A practical simulation result for two-way pushdown automata
- Two nonlinear lower bounds for on-line computations
- Efficient Simulations by Queue Machines
- Not all planar digraphs have small cycle separators
- Queue Automata: Foundations and Developments
- Title not available (Why is that?)
- On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines
- Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
This page was built for publication: Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1113670)
