scientific article; zbMATH DE number 3988713

MaRDI QIDQ3751011zbMATH OpenFDO

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

Publication date 1986

zbMATH Keywords

stacksqueuestapesfirst-in-first-out storageoff-line machines with a one-way input

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The Power of the Queue
• Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
• Efficient Simulations by Queue Machines
• On the power of several queues
• scientific article; zbMATH DE number 176494

Cited in

(14)

• Bad luck when joining the shortest queue
• The Power of the Queue
• k\(+1\) heads are better than k for PDAs
• Diving into the queue
• 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
• The linked list representation of \(n\) LIFO-stacks and/or FIFO-queues in the single-level memory
• The Power of Priority Channel Systems
• Efficient Simulations by Queue Machines
• Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
• The complexity of matrix transposition on one-tape off-line Turing machines
• The complexity of matrix transposition on one-tape off-line Turing machines with output tape

This page was built for publication:

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