Two Nonlinear Bounds for On-Line Computations
Pavol Ďuriš, Zvi Galil, Wolfgang J. Paul, Ruediger Reischuk · 1983
We prove the following lower bounds for on-line computation. 1) Simulating two tape nondeterministic machines by one tape machine requires n(n log n) time. 2) Simulating k tape (deterministic) machines by machines with k pushdown stores requires n(n log 1/(k+l) n) time.