Efficient Simulations by Queue Machines

DOI10.1137/S0097539799350608MaRDI QIDQ5470725zbMATH OpenFDO

Authors Holger Petersen, John Michael Robson

Publication date 1 June 2006

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

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

zbMATH Keywords

grammarsmultiqueue machinesmultitape machinespushdown automatasimulationupper bounds

Mathematics Subject Classification ID

Recommendations

• On the power of several queues
• scientific article; zbMATH DE number 176494
• Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
• scientific article; zbMATH DE number 3988713
• The Power of the Queue

Cited in

(10)

• Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
• On efficient simulations of multicounter machines
• The hedge: an efficient storage device for Turing machines with one head
• scientific article; zbMATH DE number 3988713 (Why is no real title available?)
• The Power of the Queue
• scientific article; zbMATH DE number 176494 (Why is no real title available?)
• Queue Automata: Foundations and Developments
• The Queuiac: An Electromechanical Analog for the Simulation of Waiting-Line Problems
• On the power of several queues
• On two-tape real-time computation and queues

This page was built for publication: Efficient Simulations by Queue Machines

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