{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:13:35Z","timestamp":1725455615416},"publisher-location":"Berlin\/Heidelberg","reference-count":19,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540537090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0020788","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:07:52Z","timestamp":1131862072000},"page":"64-75","source":"Crossref","is-referenced-by-count":0,"title":["On the power of several queues"],"prefix":"10.1007","author":[{"given":"Martin","family":"Schmidt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","unstructured":"St\u00e5l O. Aanderaa. On k-tape versus (k \u2212 1)-tape real time computation. In SIAM-AMS Proceedings, volume 7: Complexity of Computation, pages 75\u201396, 1974."},{"key":"6_CR2","volume-title":"Structural Complexity, volume 11 and 22 of EATCS Monographs on Theoretical Computer Science","author":"J. L. Balc\u00e1zar","year":"1988","unstructured":"Jos\u00e9 Luis Balc\u00e1zar, Josep D\u00e1z, and Joaquim Gabarr\u00f3. Structural Complexity, volume 11 and 22 of EATCS Monographs on Theoretical Computer Science. Springer, Berlin, 1988\u201390."},{"key":"6_CR3","volume-title":"Theories of Computational Complexity, volume 35 of Annals of Discrete Mathematics","author":"C. Calude","year":"1988","unstructured":"Cristian Calude. Theories of Computational Complexity, volume 35 of Annals of Discrete Mathematics. Elsevier North-Holland, Amsterdam, 1988."},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(84)80019-4","volume":"60","author":"P. \u010e\u016bri\u0161","year":"1984","unstructured":"Pavol \u010e\u016bri\u0161, Zvi Galil, Wolfgang Johannes Paul, and Karl R\u00fcdiger Reischuk. Two nonlinear lower bounds. Information and Control, 60:1\u201311, 1984.","journal-title":"Information and Control"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0020-0190(89)90160-9","volume":"33","author":"M. Dietzfelbinger","year":"1989","unstructured":"Martin Dietzfelbinger. The speed of copying on one-tape off-line Turing machines. Information Processing Letters, 33:83\u201389, 1989\/90.","journal-title":"Information Processing Letters"},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/S0019-9958(65)90399-2","volume":"8","author":"F. C. Hennie","year":"1965","unstructured":"Frederick C. Hennie. One-tape, off-line Turing machine computations. Information and Control, 8:553\u2013578, 1965.","journal-title":"Information and Control"},{"key":"6_CR7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1109\/PGEC.1966.264374","volume":"15","author":"F. C. Hennie","year":"1966","unstructured":"Frederick C. Hennie. On-line Turing machine computations. IEEE Transactions on Electronic Computers, 15:35\u201344, 1966.","journal-title":"IEEE Transactions on Electronic Computers"},{"key":"6_CR8","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"Juris Hartmanis and Richard E. Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285\u2013306, 1965.","journal-title":"Transactions of the American Mathematical Society"},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/321356.321362","volume":"13","author":"F. C. Hennie","year":"1966","unstructured":"Frederick C. Hennie and Richard E. Stearns. Two-tape simulation of multitape Turing machines. Journal of the ACM, 13:533\u2013546, 1966.","journal-title":"Journal of the ACM"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0022-0000(88)90047-5","volume":"37","author":"M. Li","year":"1988","unstructured":"Ming Li. Simulating two pushdown stores by one tape in $$O(n^{1.5} \\sqrt {\\log n} )$$ time. Journal of Computer and System Sciences, 37:101\u2013116, 1988. also: 26 th FOCS 1985.","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Ming Li, Luc Longpr\u00e9, and Paul M. B. Vit\u00e1nyi. The power of the queue. In 1 st Structure in Complexity Theory, pages 219\u2013233. ACM, IEEE, 1986.","DOI":"10.1007\/3-540-16486-3_101"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/0890-5401(88)90003-X","volume":"78","author":"M. Li","year":"1988","unstructured":"Ming Li and Paul M. B. Vit\u00e1nyi. Tape versus queue and stacks: The lower bounds. Information and Computation, 78:56\u201385, 1988.","journal-title":"Information and Computation"},{"key":"6_CR13","first-page":"187","volume-title":"Handbook of Theoretical Computer Science","author":"M. Li","year":"1990","unstructured":"Ming Li and Paul M. B. Vit\u00e1nyi. Kolmogorov complexity and its applications. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity, pages 187\u2013254. Elsevier North-Holland, Amsterdam, 1990."},{"key":"6_CR14","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1090\/S0002-9947-1985-0808746-4","volume":"292","author":"W. Maass","year":"1985","unstructured":"Wolfgang Maass. Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines. Transactions of the American Mathematical Society, 292:675\u2013693, 1985.","journal-title":"Transactions of the American Mathematical Society"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Wolfgang Maass, Georg Schnitger, and Endre Szemer\u00e9di. Two tapes are better than one for off-line Turing machines. In 19 th STOC, pages 94\u2013100. ACM, 1987.","DOI":"10.1145\/28395.28406"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(82)91055-5","volume":"53","author":"W. J. Paul","year":"1982","unstructured":"Wolfgang Johannes Paul. On-line simulation of k+1 tapes by k tapes requires nonlinear time. Information and Control, 53:1\u20138, 1982.","journal-title":"Information and Control"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/0022-0000(81)90009-X","volume":"23","author":"W. J. Paul","year":"1981","unstructured":"Wolfgang Johannes Paul, Joel I. Seiferas, and Janos Simon. An information theoretic approach to time bounds for on-line computation. Journal of Computer and System Sciences, 23:108\u2013126, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR18","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF02759719","volume":"1","author":"M. O. Rabin","year":"1963","unstructured":"Michael O. Rabin. Real time computation. Israel Journal of Mathematics, 1:203\u2013211, 1963.","journal-title":"Israel Journal of Mathematics"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-0000(84)90001-1","volume":"29","author":"P. M. B. Vit\u00e1nyi","year":"1984","unstructured":"Paul M. B. Vit\u00e1nyi. On two-tape real-time computation and queues. Journal of Computer and System Sciences, 29:303\u2013311, 1984.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","STACS 91"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0020788.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:44:56Z","timestamp":1607550296000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0020788"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540537090"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0020788","relation":{},"subject":[]}}