The Power of the Queue

DOI10.1137/0221042zbMath0749.68031OpenAlexW2168631241MaRDI QIDQ4016402

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

upper boundslower boundson-line simulationabstract storage unitmulti-queue machinesmulti-tape machines

Mathematics Subject Classification ID

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

Related Items (7)

Fast nondeterministic recognition of context-free languages using two queues ⋮ Reversible and Irreversible Computations of Deterministic Finite-State Devices ⋮ Queue Automata: Foundations and Developments ⋮ Freezing 1-Tag Systems with States ⋮ On the power of several queues ⋮ PROGRAMMED GRAMMARS WITH RULE QUEUES ⋮ ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS

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