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

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)

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)

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

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)