ylfink@water.UUCP (05/26/87)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
COMPUTATIONAL COMPLEXITY SEMINAR
- Thursday, May 28, 1987
Dr. Luc Longpre of the University of Washington, will
speak on ``The Power of the Queue''.
TIME: 3:30 PM
ROOM: MC 3005
ABSTRACT
Queues, stacks and tapes are basic concepts which have
direct applications in compiler design and the general
design of algorithms. Whereas stacks (pushdown store
or last-in-first-out storage) have been thoroughly
investigated and are well understood, this is much less
the case for queues (first-in-first-out storage).
In this talk, we compare the power of queues to that of
stacks and tapes. We address off-line machines with a
one-way input. In particular, 1 queue and 1 tape (or
stack) are not comparable:
(1) Simulating 1 stack (and hence 1 tape) by 1 queue
requires OMEGA(n sup 4/3 / log n) time in both the
deterministic and the nondeterministic cases.
(2) Simulating 1 queue by 1 tape requires OMEGA(n sup 2
) time in the deterministic case, and OMEGA(n sup
4/3 / (log n) sup 2/3) in the nondeterministic
case.
We use Kolmogorov complexity techniques to prove the
lower bounds. Knowledge of Kolmogorov complexity is
not assumed from the audience. We start with a simple
example on how to use this technique.
May 26, 1987