{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:24:19Z","timestamp":1787502259530,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540164869","type":"print"},{"value":"9783540398257","type":"electronic"}],"license":[{"start":{"date-parts":[[1986,1,1]],"date-time":"1986-01-01T00:00:00Z","timestamp":504921600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_101","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:45:14Z","timestamp":1330177514000},"page":"219-233","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["The power of the queue"],"prefix":"10.1007","author":[{"given":"Ming","family":"Li","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luc","family":"Longpr\u00e9","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul M. B.","family":"Vit\u00e1nyi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"17_CR1","unstructured":"Aanderaa, S.O., \"On k-tape versus (k-1)-tape real-time computation,\" in Complexity of Computation, ed. R.M. Karp, SIAM-AMS Proceedings, vol. 7, pp. 75\u201396, American Math. Society, Providence, R.I., 1974."},{"key":"17_CR2","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1016\/S0022-0000(70)80031-9","volume":"4","author":"R. Book","year":"1970","unstructured":"Book, R., S. Greibach, and B. Wegbreit, \"Time-and tape-bound Turing acceptors and AFL's,\" J. Computer and System Sciences, vol. 4, pp. 606\u2013621, 1970.","journal-title":"J. Computer and System Sciences"},{"key":"17_CR3","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1147\/rd.214.0350","volume":"21","author":"G.J. Chaitin","year":"1977","unstructured":"Chaitin, G.J., \"Algorithmic Information Theory,\" IBM J. Res. Dev., vol. 21, pp. 350\u2013359, 1977.","journal-title":"IBM J. Res. Dev."},{"key":"17_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(84)80019-4","volume":"60","author":"P. Duris","year":"1984","unstructured":"Duris, P., Z. Galil, W. Paul, and R. Reischuk, \"Two nonlinear lower bounds for on-line computations,\" Information and Control, vol. 60, pp. 1\u201311, 1984.","journal-title":"Information and Control"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Galil, Z., R. Kannan, E. Szemeredi, \u201cOn nontrivial separators for k-page graphs and simulations by non-deterministic one-tape Turing machines,\u201d in Proceedings 18th Annual ACM Symposium on Theory of Computing, 1986.","DOI":"10.1145\/12130.12135"},{"key":"17_CR6","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1969","unstructured":"Hartmanis, J. and R.E. Stearns, \"On the computational complexity of algorithms,\" Trans. Amer. Math. Soc., vol. 117, pp. 285\u2013306, 1969.","journal-title":"Trans. Amer. Math. Soc."},{"key":"17_CR7","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/321356.321362","volume":"4","author":"F.C. Hennie","year":"1966","unstructured":"Hennie, F.C. and R.E. Stearns, \"Two tape simulation of multitape Turing machines,\" J. Ass. Comp. Mach., vol. 4, pp. 533\u2013546, 1966.","journal-title":"J. Ass. Comp. Mach."},{"key":"17_CR8","unstructured":"Hopcroft, J.E. and J.D. Ullman, Formal Languages and their Relations to Automata, Addison-Wesley, 1969."},{"issue":"4","key":"17_CR9","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1137\/0213011","volume":"13","author":"M. Klawe","year":"1984","unstructured":"Klawe, M., \"Limitations on explicit construction of expanding graphs,\" SIAM J. Comp., vol. 13, no. 4, pp. 156\u2013166, 1984.","journal-title":"SIAM J. Comp."},{"issue":"1","key":"17_CR10","first-page":"1","volume":"1","author":"A.N. Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.N., \"Three approaches to the quantitative definition of information,\" Problems in Information Transmission, vol. 1, no. 1, pp. 1\u20137, 1965.","journal-title":"Problems in Information Transmission"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Li, M., \"Simulating two pushdowns by one tape in O(n**1.5 (log n)**0.5) time,\" 26th Annual IEEE Symposium on the Foundations of Computer Science, 1985.","DOI":"10.1109\/SFCS.1985.50"},{"key":"17_CR12","unstructured":"Li, M., \"Lower Bounds in Computational Complexity,\" Ph.D. Thesis, Report TR-85-663, Computer Science Department, Cornell University, march 1985."},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Li, M., \"Lower bounds by Kolmogorov-complexity\", 12th ICALP, Lecture Notes in Computer Science, 194, pp. 383\u2013393, 1985.","DOI":"10.1007\/BFb0015764"},{"key":"17_CR14","unstructured":"Li, M. and P.M.B. Vitanyi, \"Tape versus queue and stacks: The lower bounds,\" Submitted for publication."},{"key":"17_CR15","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1145\/322234.322246","volume":"28","author":"B.L. Leong","year":"1981","unstructured":"Leong, B.L. and J.I. Seiferas, \"New real-time simulations of mul-tihead tape units,\" J. Ass. Comp. Mach., vol. 28, pp. 166\u2013180, 1981.","journal-title":"J. Ass. Comp. Mach."},{"issue":"2","key":"17_CR16","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1090\/S0002-9947-1985-0808746-4","volume":"292","author":"W. Maass","year":"1985","unstructured":"Maass, W., \"Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines,\" Trans. Amer. Math. Soc., 292,2, pp. 675\u2013693, 1985. (Preliminary Version \u201cQuadratic lower bounds for deterministic and nondeterminstic one-tape Turing machines,\u201d pp 401\u2013408 in Proceedings 16th ACM Symposium on Theory of Computing, 1984.)","journal-title":"Trans. Amer. Math. Soc."},{"key":"17_CR17","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/0022-0000(81)90009-X","volume":"23","author":"W.J. Paul","year":"1981","unstructured":"Paul, W.J., J.I. Seiferas, and J. Simon, \"An information theoretic approach to time bounds for on-line computation,\" J. Computer and System Sciences, vol. 23, pp. 108\u2013126, 1981.","journal-title":"J. Computer and System Sciences"},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"Paul, W.J., \"On-line simulation of k+1 tapes by k tapes requires nonlinear time,\" Information and Control, pp. 1\u20138, 1982.","DOI":"10.1016\/S0019-9958(82)91055-5"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(64)90223-2","volume":"7","author":"R. Solomonov","year":"1964","unstructured":"Solomonov, R., Information and Control, vol. 7, pp. 1\u201322, 1964.","journal-title":"Information and Control"},{"key":"17_CR20","unstructured":"Vit\u00e1nyi, P.M.B., \"One queue or two pushdown stores take square time on a one-head tape unit,\" Computer Science Technical Report CS-R8406, CWI, Amsterdam, March 1984."},{"key":"17_CR21","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(85)90020-1","volume":"21","author":"P.M.B. Vit\u00e1nyi","year":"1985","unstructured":"Vit\u00e1nyi, P.M.B., \"An N**1.618 lower bound on the time to simulate one queue or two pushdown stores by one tape,\" Information Processing Letters, vol. 21, pp. 147\u2013152, 1985.","journal-title":"Information Processing Letters"},{"key":"17_CR22","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0022-0000(84)90001-1","volume":"29","author":"P.M.B. Vit\u00e1nyi","year":"1984","unstructured":"Vit\u00e1nyi, P.M.B., \"On two-tape real-time computation and queues,\" J. Computer and System Sciences, vol. 29, pp. 303\u2013311, 1984.","journal-title":"J. Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T08:39:17Z","timestamp":1558255157000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_101","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}