Accession Number:

ADA171536

Title:

The Power of the Queue.

Descriptive Note:

Interim research rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

• Li,Ming
• Longpre,Luc
• Vitanyi,Paul M.

Report Date:

1986-04-01

Pagination or Media Count:

22.0

Abstract:

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

Descriptors:

• *QUEUEING THEORY
• ALGORITHMS
• INPUT
• TAPES
• COMPILERS
• STACKING
• OFFLINE SYSTEMS

Subject Categories:

• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE