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 log1/k+1) n) time.
--Authors’ Abstract
--Abstract recommended by J. Hartmanis, Ithaca, NY