Two nonlinear lower bounds for on-line computations
From MaRDI portal
Publication:3718158
DOI10.1016/S0019-9958(84)80019-4zbMath0589.68039MaRDI QIDQ3718158
Wolfgang J. Paul, Pavol Ďuriš, Zvi Galil, K. Ruediger Reischuk
Publication date: 1984
Published in: Information and Control (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
Related Items
On the power of several queues, Milking the Aanderaa argument, On the structure of one-tape nondeterministic Turing machine time hierarchy, Tape versus queue and stacks: The lower bounds