Simulating two pushdown stores by one tape in O(n^1.5\, \,n) time
Two important results are proved in the paper: Theorem 1'. A one-tape nondeterministic Turing machine can simulate a two-pushdown store Turing machine in \(O(n^{1.5} \sqrt{\log n})\) time. Theorem 2. The languages used by \textit{W. Maass} [Trans. Am. Math. Soc. 292, 675-693 (1985; Zbl 0608.03013)] and \textit{R. Freivalds} [Inf. Process. 77, Proc. IFIP Congr., Toronto 1977, 839-842 (1977; Zbl 0367.94079)] can be accepted in \(O(n^ 2 \log \log n/\sqrt{\log n})\) time by a one-tape nondeterministic on-line machine. Theorem 1' disproves the conjectured \(O(n^ 2)\) lower bound which holds for the deterministic case. The proof is based on the separator theorem for planar graphs [\textit{R. J. Lipton} and \textit{R. E. Tarjan}, SIAM J. Appl. Math. 36, 177-189 (1979; Zbl 0432.05022)]. Theorem 2 shows that the \(O(n^ 2)\) lower bound cannot be obtained for one-tape nondeterministically simulating two tapes. The proof is based on the separator theorem for doubling transformation graphs (a proof of this theorem is given in the paper). As applications the following results are obtained: three pushdown stores are better than two pushdown stores for nondeterministic machines and one tape can nondeterministically simulate one nondeterministic queue in \(O(n^{1.5} \sqrt{\log n})\) time. A list of three open questions ends the paper.
- A Separator Theorem for Planar Graphs
- An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
- Applications of a Planar Separator Theorem
- Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
- scientific article; zbMATH DE number 3913680 (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?)
- Limitations on Explicit Constructions of Expanding Graphs
- On the Computational Complexity of Algorithms
- On-line simulation of k + 1 tapes by k tapes requires nonlinear time
- One-way stack automata
- Quasi-realtime languages
- Real time computation
- Tape versus queue and stacks: The lower bounds
- Time- and tape-bounded Turing acceptors and AFLs
- Two Tapes are Better than One for Nondeterministic Machines
- Two-Tape Simulation of Multitape Turing Machines
- On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines
- Not all planar digraphs have small cycle separators
- Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
- A practical simulation result for two-way pushdown automata
- Two Tapes are Better than One for Nondeterministic Machines
- Two nonlinear lower bounds for on-line computations
- scientific article; zbMATH DE number 4126702 (Why is no real title available?)
- scientific article; zbMATH DE number 4117867 (Why is no real title available?)
- Simulation of two-way pushdown automata revisited
- Queue Automata: Foundations and Developments
- Efficient Simulations by Queue Machines
- On the power of several queues
- Milking the Aanderaa argument
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)
