The following lower bounds for on-line computation are proved: (1) Simulating two-tape nondeterministic machines by one-tape machines requires &OHgr;(n log n) time. (2) Simulating k-tape (deterministic) machines by machines with k-pushdown stores requires &OHgr;(n log^1/k+1) n) time.

--Authors’ Abstract

--Abstract recommended by J. Hartmanis, Ithaca, NY