The Power of the Queue.
Interim research rept.,
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Pagination or Media Count:
Queues, stacks pushdown stores, and tapes are storage models which 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. 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 rely on algorithmic information theory Kolmogorov Complexity. Author
- Computer Programming and Software