Simulating two pushdown stores by one tape in O(n^1.5\, \,n) time

DOI10.1016/0022-0000(88)90047-5MaRDI QIDQ1113670zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

complexityqueuesseparator theoremnondeterministic Turing machinetwo-pushdown store Turing machine

Mathematics Subject Classification ID

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)

Recommendations

• On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines
• Publication:4206403
• Two nonlinear lower bounds for on-line computations
• Milking the Aanderaa argument
• scientific article; zbMATH DE number 4078813

Cites work

• 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?)
• 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
• 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

Cited in

(13)

• scientific article; zbMATH DE number 4126702 (Why is no real title available?)
• 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
• Not all planar digraphs have small cycle separators
• Efficient Simulations by Queue Machines
• Queue Automata: Foundations and Developments
• scientific article; zbMATH DE number 4117867 (Why is no real title available?)
• 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)