The Power of the Queue
Author(s)
Li, Ming; Longpre, Luc; Vitányi, Paul M.B.![Thumbnail](/bitstream/handle/1721.1/149112/MIT-LCS-TM-303.pdf.jpg?sequence=3&isAllowed=y)
DownloadMIT-LCS-TM-303.pdf (5.139Mb)
Metadata
Show full item recordAbstract
Queues, stacks (pushdown stores), and tapes are storage models which have direct applications in compiler design and the general desig 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). This paper contains a comprehensive study comparing queues to stacks and tapes. We address off-line machines with a one-way input, both deterministic and nondeterministic. The techniques relly on algorithmic information theory (Kolmogorov Complexity).
Date issued
1986-04Series/Report no.
MIT-LCS-TM-303