Milking the Aanderaa argument

DOI10.1016/0890-5401(90)90005-3zbMath0705.68050OpenAlexW2161916043MaRDI QIDQ918198

Richard E. Newman-Wolfe, Ramamohan Paturi, Janos Simon, Joel I. Seiferas

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1802/5963

zbMATH Keywords

lower boundson-line simulationpushdown stores

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (1)

On the power of several queues

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An information-theoretic approach to time bounds for on-line computation
• Real time computation
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• Two nonlinear lower bounds for on-line computations
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Two-Tape Simulation of Multitape Turing Machines
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

This page was built for publication: Milking the Aanderaa argument