1983 Reports

Two Nonlinear Bounds for On-Line Computations

Duris, Pavol; Galil, Zvi; Paul, Wolfgang; Reischuk, Ruediger

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.