|
|||||
|
|
An n1.618 lower bound on the time to simulate one queue or two pushdown stores by one tape |
|
| Authors: | Paul M.B. Vitányi |
| Affiliation: | Department of Computer Science, Centre for Mathematics and Computer Science (C.W.I.), Kruislaan 413, 1098 SJ Amsterdam, The Netherlands |
| Abstract: | To simulate two pushdown stores, or one queue, on-line by a one-head tape unit requires Ω(n1.618) time. |
| Keywords: | Multiple Turing machines pushdown stores queues time complexity lower bounds on-line simulation by single-head tape units Kolmogorov complexity 68C40 68C25 68C05 94B60 10-00 F.1.1 F.1.3 F.2.3 |
| 本文献已被 ScienceDirect 等数据库收录！ | |