The Power of the Queue

DOI10.1137/0221042MaRDI QIDQ4016402zbMATH OpenOpenAlexFDO

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

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

abstract storage unitlower boundsmulti-queue machinesmulti-tape machineson-line simulationupper bounds

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3988713
• On the power of several queues
• Efficient Simulations by Queue Machines
• Tape versus queue and stacks: The lower bounds
• scientific article; zbMATH DE number 176494

Cited in

(15)

• Tape versus queue and stacks: The lower bounds
• Bad luck when joining the shortest queue
• Fast nondeterministic recognition of context-free languages using two queues
• Reversible and irreversible computations of deterministic finite-state devices
• Programmed grammars with rule queues
• scientific article; zbMATH DE number 3988713 (Why is no real title available?)
• scientific article; zbMATH DE number 176494 (Why is no real title available?)
• scientific article; zbMATH DE number 1796967 (Why is no real title available?)
• Queue Automata: Foundations and Developments
• Diving into the queue
• On the leftmost derviation in matrix grammars
• Efficient Simulations by Queue Machines
• The Power of Priority Channel Systems
• Freezing 1-Tag Systems with States
• On the power of several queues

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)