On One Tape Versus Two Stacks

We develop a simple method which enables us to prove three new lower bounds (for both worst and average cases) for on-line computations, answering two open problems summarized in [DGPR]. We give a language that requires $\Omega (n^{2})$ time for any 1-tape deterministic on-line machine, but it can be accepted by a 2-stack 1-reversal bounded deterministic on-line machine in real time. This provides a tight lower bound, closing the gap between $\Omega ( n(logn)^{1/2})$ lower bound by [P2] and the trivial $O(n^{2})$ upper bound. We also prove that 1-tape nondeterministic real time is much stronger than its deterministic version. For 1-tape on-line machines, we give language L (L") which is in nondeterministic linear (real) time but requires $\Omega(n^{2})(\Omega (n^{1.5}))$ deterministic time. Finally we give a language which can be accepted by a 2-stack 1-reversal bounded deterministic machine in real time, but it requires $\Omega(n^{1+1/2})$ time for any one tape nondeterministic online machine. This sharply improves an $nlogn$ lower bound in [DGPR]