On the power of several queues
| Autor: | Martin Hühne |
|---|---|
| Rok vydání: | 1993 |
| Předmět: |
NTIME
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES General Computer Science Kolmogorov complexity DTIME Probabilistic Turing machine 2-EXPTIME Computer science Linear speedup theorem NSPACE DSPACE law.invention Theoretical Computer Science Combinatorics symbols.namesake Turing machine Turing reduction law symbols Universal Turing machine Time hierarchy theorem Alternating Turing machine PSPACE Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 113(1):75-91 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/0304-3975(93)90211-b |
| Popis: | We present almost matching upper and lower time bounds for the simulation of Turing machines with many queues, tapes, or stacks on Turing machines with few queues. In particular, the power of two queues in comparison with other storage types is clarified. We show that t ( n )-time-bounded multistorage Turing machines can be simulated in time O( t ( n ) 1 + 1/ k ) on k -queue machines. Every online simulation of k + 1 queues (or of two tapes) on k queues requires time Ω( t ( n ) 1 + 1/ k /polylog t ( n )). The lower bounds are based on Kolmogorov complexity. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|