The Power of the Queue
Authors:
- Ming LiMLMing Li
- Luc LongpréLLLuc Longpré
- Paul VitányiPVPaul Vitányi
- 1 August 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (4) , 697-712
Abstract
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). In this paper 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 ^2 n\log \log n))$ in the nondeterministic case. The deterministic bound is tight. The nondeterministic one is almost tight. The upper bounds for queues are also obtained.
Keywords
This publication has 24 references indexed in Scilit:
- Two nonlinear lower bounds for on-line computationsInformation and Control, 1984
- The complexity of sorting on distributed systemsInformation and Control, 1984
- Limitations on Explicit Constructions of Expanding GraphsSIAM Journal on Computing, 1984
- Real-time queue operations in pure LISPInformation Processing Letters, 1981
- Algorithmic Information TheoryIBM Journal of Research and Development, 1977
- Universal codeword sets and representations of the integersIEEE Transactions on Information Theory, 1975
- Time- and tape-bounded turing acceptors and AFLsJournal of Computer and System Sciences, 1970
- Quasi-realtime languagesTheory of Computing Systems, 1970
- Two-Tape Simulation of Multitape Turing MachinesJournal of the ACM, 1966
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965