The Power of the Queue.

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1986
Accession Number
ADA171536

Entities

People

  • Luc Longpre
  • Ming Li
  • Paul M. Vitanyi

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Weapons Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Boundaries
  • Classification
  • Compilers
  • Computational Complexity
  • Computer Science
  • Computers
  • Formal Languages
  • Information Processing
  • Information Science
  • Information Theory
  • Language
  • Machines
  • Military Research
  • Simulations
  • Universities

Fields of Study

  • Computer science

Readers

  • Computer Programming and Software Development.
  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Mathematical Modeling and Probability Theory.