×

The power of the queue. (English) Zbl 0749.68031

Summary: Queues, stacks, and tapes are basic concepts that 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).
A comprehensive study comparing queues to stacks and tapes (off-line and with a one-way input tape) is presented. The techniques used rely on Kolmogorov complexity. In particular, one queue and one tape (or stack) are incomparable:
(1) Simulating one stack (and hence one tape) by one queue requires \(\Omega (n^{4/3}/\log n)\) time in both the deterministic and the nondeterministic cases. A corollary of this lower bound states that for this model of one-queue machines, nondeterministic linear time is not closed under complement.
(2) Simulating one queue by one tape requires \(\Omega (n^ 2)\) time in the deterministic case and requires \(\Omega (n^{4/3}/(\log n)^{2/3})\)in the nondeterministic case.
The paper further compares the relative power between different numbers of queues:
(3) Simulating two queues (or two tapes) by one queue requires \(\Omega (n^ 2)\) time in the deterministic case, and \(\Omega (n^ 2/(\log^ 2n\log\log n))\) in the nondeterministic case. The deterministic bounds is tight. The nondeterministic one is almost tight. The upper bounds for queues are also obtained.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
68P05 Data structures
PDFBibTeX XMLCite
Full Text: DOI