Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!ylfink
From: ylfink@water.UUCP
Newsgroups: ont.events,uw.talks
Subject: The Power of the Queue.
Message-ID: <963@water.UUCP>
Date: Tue, 26-May-87 09:38:11 EDT
Article-I.D.: water.963
Posted: Tue May 26 09:38:11 1987
Date-Received: Wed, 27-May-87 01:13:47 EDT
Distribution: ont
Organization: U of Waterloo, Ontario
Lines: 46
Keywords: CS, U of W, Dr. L. Longpre, Thurs., May 28, 1987, 3:30PM, MC 3005.
Xref: utgpu ont.events:695 junk:5137



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