{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:27Z","timestamp":1725664467529},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540587156"},{"type":"electronic","value":"9783540490548"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58715-2_111","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:41:51Z","timestamp":1330274511000},"page":"24-35","source":"Crossref","is-referenced-by-count":1,"title":["Matching upper and lower bounds for simulations of several tapes on one multidimensional tape"],"prefix":"10.1007","author":[{"given":"Martin","family":"Dietzfelbinger","sequence":"first","affiliation":[]},{"given":"Martin","family":"H\u00fchne","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0020-0190(89)90160-9","volume":"33","author":"M. Dietzfelbinger","year":"1989\/90","unstructured":"M. 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":"3_CR2","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1109\/PGEC.1966.264374","volume":"15","author":"F.C. Hennie","year":"1966","unstructured":"F.C. Hennie. On-line Turing machine computations. IEEE Transactions on Electronic Computers, 15: 35\u201344, 1966.","journal-title":"IEEE Transactions on Electronic Computers"},{"key":"3_CR3","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/321356.321362","volume":"13","author":"F.C. Hennie","year":"1966","unstructured":"F.C. Hennie and R.E. Stearns. Two-tape simulation of multitape Turing machines. Journal of the ACM, 13: 533\u2013546, 1966.","journal-title":"Journal of the ACM"},{"key":"3_CR4","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass., 1979."},{"key":"3_CR5","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/BF01213861","volume":"25","author":"M.C. Loui","year":"1992","unstructured":"M.C. Loui and D.R. Luginbuhl. The complexity of on-line simulations between multidimensional Turing machines and random access machines. Mathematical Systems Theory, 25: 293\u2013308, 1992.","journal-title":"Mathematical Systems Theory"},{"key":"3_CR6","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-3975(81)90084-0","volume":"15","author":"M.C. Loui","year":"1981","unstructured":"M.C. Loui. A space bound for one-tape multidimensional Turing machines. Theoretical Computer Science, 15: 311\u2013320, 1981.","journal-title":"Theoretical Computer Science"},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0304-3975(89)90081-9","volume":"21","author":"M.C. Loui","year":"1982","unstructured":"M.C. Loui. Simulations among multidimensional Turing machines. Theoretical Computer Science, 21: 145\u2013161, 1982.","journal-title":"Theoretical Computer Science"},{"key":"3_CR8","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1137\/0212030","volume":"12","author":"M.C. Loui","year":"1983","unstructured":"M.C. Loui. Optimal dynamic embedding of trees into arrays. SIAM Journal on Computing, 12: 463\u2013472, 1983.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR9","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0022-0000(84)90019-9","volume":"28","author":"M.C. Loui","year":"1984","unstructured":"M.C. Loui. Minimizing access pointers into trees and arrays. Journal of Computer and System Sciences, 28: 359\u2013378, 1984.","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR10","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0890-5401(88)90003-X","volume":"78","author":"M. Li","year":"1988","unstructured":"M. Li and P.M.B. Vit\u00e1nyi. Tape versus queue and stacks: The lower bounds. Information and Computation, 78: 56\u201385, July 1988.","journal-title":"Information and Computation"},{"key":"3_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3860-5","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1993","unstructured":"M. Li and P.M.B. Vit\u00e1nyi. An Introduction to Kolmogorov Complexity and its Applications. Springer, New York, 1993."},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1090\/S0002-9947-1985-0808746-4","volume":"292","author":"W. Maass","year":"1985","unstructured":"W. Maass. Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines. Transactions of the AMS, 292: 675\u2013693, 1985.","journal-title":"Transactions of the AMS"},{"key":"3_CR13","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/BF01275490","volume":"3","author":"W. Maass","year":"1993","unstructured":"W. Maass, G. Schnitger, E. Szemer\u00e9di, and G. T\u00faran. Two tapes versus one for off-line Turing machines. Computational Complexity, 3: 392\u2013401, 1993.","journal-title":"Computational Complexity"},{"key":"3_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(83)90063-4","volume":"28","author":"W.J. Paul","year":"1984","unstructured":"W.J. Paul. On heads versus tapes. Theoretical Computer Science, 28: 1\u201312, 1984.","journal-title":"Theoretical Computer Science"},{"key":"3_CR15","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N. Pippenger","year":"1979","unstructured":"N. Pippenger and M.J. Fischer. Relations among complexity measures. Journal of the ACM, 26: 361\u2013381, 1979.","journal-title":"Journal of the ACM"},{"key":"3_CR16","first-page":"343","volume":"23","author":"W.J. Paul","year":"1981","unstructured":"W.J. Paul, J.I. Seiferas, and J. Simon. An information-theoretic approach to time bounds for online computation. J. Computer and System Sciences, 23: 343\u2013350, 1981.","journal-title":"J. Computer and System Sciences"},{"key":"3_CR17","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0304-3975(82)90037-8","volume":"19","author":"K.R. Reischuk","year":"1982","unstructured":"K.R. Reischuk. A fast implementation of a multidimensional storage into a tree storage. Theoretical Computer Science, 19: 253\u2013266, 1982.","journal-title":"Theoretical Computer Science"},{"key":"3_CR18","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/0890-5401(89)90037-0","volume":"81","author":"W. Schnitzlein","year":"1989","unstructured":"W. Schnitzlein and H.-J. Stoss. Linear-time simulation of multihead Turing machines. Information and Computation, 81: 353\u2013363, 1989.","journal-title":"Information and Computation"},{"key":"3_CR19","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1007\/BF02242349","volume":"7","author":"H.J. Stoss","year":"1971","unstructured":"H.J. Stoss. Zwei-Band Simulation von Turingmaschinen. Computing, 7: 222\u2013235, 1971.","journal-title":"Computing"},{"key":"3_CR20","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/31846.32978","volume":"34","author":"P. Tiwari","year":"1987","unstructured":"P. Tiwari. Lower bounds on communication complexity in distributed computer networks. Journal of the ACM, 34: 921\u2013938, 1987.","journal-title":"Journal of the ACM"},{"key":"3_CR21","volume-title":"Computational Complexity","author":"K. Wagner","year":"1985","unstructured":"K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, Dordrecht, 1985."}],"container-title":["Lecture Notes in Computer Science","Foundation of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58715-2_111.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:20:00Z","timestamp":1619572800000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58715-2_111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540587156","9783540490548"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-58715-2_111","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}