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.


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