Two nonlinear lower bounds for on-line computations

DOI10.1016/S0019-9958(84)80019-4MaRDI QIDQ3718158zbMATH OpenFDO

Authors Pavol Ďuriš, Wolfgang J. Paul, Zvi Galil, Rüdiger Reischuk

Publication date 1984

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(84)80019-4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
• Milking the Aanderaa argument
• Tape versus queue and stacks: The lower bounds
• scientific article; zbMATH DE number 3913680

Cited in

(8)

• On the structure of one-tape nondeterministic Turing machine time hierarchy
• Tape versus queue and stacks: The lower bounds
• Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
• Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• scientific article; zbMATH DE number 3913680 (Why is no real title available?)
• On the power of several queues
• Milking the Aanderaa argument

This page was built for publication: Two nonlinear lower bounds for on-line computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3718158)