The Power of the Queue
Queues, stacks (pushdown stores), and tapes are storage models which have direct applications in compiler design and the general desig of algorithms. Whereas stacks (pushdown store or last-in-first-out storage) have been thoroughly investigated and are well understood, this is much less the case for...
| Main Authors: | , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149112 |
| _version_ | 1811083601559683072 |
|---|---|
| author | Li, Ming Longpre, Luc Vitányi, Paul M.B. |
| author_facet | Li, Ming Longpre, Luc Vitányi, Paul M.B. |
| author_sort | Li, Ming |
| collection | MIT |
| description | Queues, stacks (pushdown stores), and tapes are storage models which have direct applications in compiler design and the general desig of algorithms. Whereas stacks (pushdown store or last-in-first-out storage) have been thoroughly investigated and are well understood, this is much less the case for queues (first-in-first-out storage). This paper contains a comprehensive study comparing queues to stacks and tapes. We address off-line machines with a one-way input, both deterministic and nondeterministic. The techniques relly on algorithmic information theory (Kolmogorov Complexity). |
| first_indexed | 2024-09-23T12:35:40Z |
| id | mit-1721.1/149112 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T12:35:40Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1491122023-03-30T03:44:38Z The Power of the Queue Li, Ming Longpre, Luc Vitányi, Paul M.B. Queues, stacks (pushdown stores), and tapes are storage models which have direct applications in compiler design and the general desig of algorithms. Whereas stacks (pushdown store or last-in-first-out storage) have been thoroughly investigated and are well understood, this is much less the case for queues (first-in-first-out storage). This paper contains a comprehensive study comparing queues to stacks and tapes. We address off-line machines with a one-way input, both deterministic and nondeterministic. The techniques relly on algorithmic information theory (Kolmogorov Complexity). 2023-03-29T14:28:12Z 2023-03-29T14:28:12Z 1986-04 https://hdl.handle.net/1721.1/149112 MIT-LCS-TM-303 application/pdf |
| spellingShingle | Li, Ming Longpre, Luc Vitányi, Paul M.B. The Power of the Queue |
| title | The Power of the Queue |
| title_full | The Power of the Queue |
| title_fullStr | The Power of the Queue |
| title_full_unstemmed | The Power of the Queue |
| title_short | The Power of the Queue |
| title_sort | power of the queue |
| url | https://hdl.handle.net/1721.1/149112 |
| work_keys_str_mv | AT liming thepowerofthequeue AT longpreluc thepowerofthequeue AT vitanyipaulmb thepowerofthequeue AT liming powerofthequeue AT longpreluc powerofthequeue AT vitanyipaulmb powerofthequeue |