The Power of the Queue

DOI10.1137/0221042zbMATH Open0749.68031OpenAlexW2168631241MaRDI QIDQ4016402FDOQ4016402

Ming Li, Luc Longpré, Paul M. B. Vitányi

Publication date: 14 December 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221042

zbMATH Keywords

lower boundsupper boundson-line simulationabstract storage unitmulti-queue machinesmulti-tape machines

Mathematics Subject Classification ID

Data structures (68P05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cited In (12)

• Bad luck when joining the shortest queue
• Reversible and Irreversible Computations of Deterministic Finite-State Devices
• Diving into the queue
• Fast nondeterministic recognition of context-free languages using two queues
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the power of several queues
• Freezing 1-Tag Systems with States
• The Power of Priority Channel Systems
• ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS
• Queue Automata: Foundations and Developments
• PROGRAMMED GRAMMARS WITH RULE QUEUES

   Recommendations

• Title not available (Why is that?) 👍 👎
• On the power of several queues 👍 👎
• Efficient Simulations by Queue Machines 👍 👎
• Tape versus queue and stacks: The lower bounds 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: The Power of the Queue

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4016402)