##
**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.

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 |