{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T15:21:12Z","timestamp":1725895272436},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540882817"},{"type":"electronic","value":"9783540882824"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-88282-4_39","type":"book-chapter","created":{"date-parts":[[2008,9,24]],"date-time":"2008-09-24T07:46:38Z","timestamp":1222242398000},"page":"433-439","source":"Crossref","is-referenced-by-count":1,"title":["Sorting and Element Distinctness on One-Way Turing Machines"],"prefix":"10.1007","author":[{"given":"Holger","family":"Petersen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s00236-003-0125-8","volume":"40","author":"A.M. Ben-Amram","year":"2003","unstructured":"Ben-Amram, A.M., Berkman, O., Petersen, H.: Element distinctness on one-tape Turing machines. Acta Informatica\u00a040, 81\u201394 (2003)","journal-title":"Acta Informatica"},{"key":"39_CR2","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0304-3975(91)90175-2","volume":"82","author":"M. Dietzfelbinger","year":"1991","unstructured":"Dietzfelbinger, M., Maass, W., Schnitger, G.: The complexity of matrix transposition on one-tape off-line Turing machines. Theoretical Computer Science\u00a082, 113\u2013129 (1991)","journal-title":"Theoretical Computer Science"},{"key":"39_CR3","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with O(1) worst case access time. Journal of the Association for Computing Machinery\u00a031, 538\u2013544 (1984)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"Kalyanasundaram, B., Schnitger, G.: Communication complexity and lower bounds for sequential machines. In: Buchmann, J., Ganzinger, H., Paul, W.J. (eds.) Informatik \u2013 Eine Festschrift zum 60. Geburtstag von G\u00fcnter Hotz, Teubner, Stuttgart. Teubner-Texte zur Informatik, vol.\u00a01, pp. 253\u2013268 (1992)","DOI":"10.1007\/978-3-322-95233-2_15"},{"key":"39_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0020-0190(94)00111-1","volume":"51","author":"A. L\u00f3pez-Ortiz","year":"1994","unstructured":"L\u00f3pez-Ortiz, A.: New lower bounds for element distinctness on a one-tape Turing machine. Information Processing Letters\u00a051, 311\u2013314 (1994)","journal-title":"Information Processing Letters"},{"key":"39_CR6","series-title":"Graduate Texts in Computer Science","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P. (eds.): An Introduction to Kolmogorov Complexity and its Applications, 2nd edn. Graduate Texts in Computer Science. Springer, Heidelberg (1997)","edition":"2"},{"key":"39_CR7","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0020-0190(01)00201-0","volume":"81","author":"H. Petersen","year":"2002","unstructured":"Petersen, H.: Bounds for the element distinctness problem on one-tape Turing machines. Information Processing Letters\u00a081, 75\u201379 (2002)","journal-title":"Information Processing Letters"},{"key":"39_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-540-77566-9_35","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"H. Petersen","year":"2008","unstructured":"Petersen, H.: Element distinctness and sorting on one-tape off-line Turing machines. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol.\u00a04910, pp. 406\u2013417. Springer, Heidelberg (2008)"},{"key":"39_CR9","unstructured":"Reischuk, K.R.: Einf\u00fchrung in die Komplexit\u00e4tstheorie. B.\u00a0G.\u00a0Teubner (1990)"},{"key":"39_CR10","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(88)90052-1","volume":"77","author":"C. Slot","year":"1988","unstructured":"Slot, C., van Emde Boas, P.: The problem of space invariance for sequential machines. Information and Computation\u00a077, 93\u2013122 (1988)","journal-title":"Information and Computation"},{"key":"39_CR11","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0020-0190(96)00108-1","volume":"59","author":"A. Szepietowski","year":"1996","unstructured":"Szepietowski, A.: The element distinctness problem on one-tape Turing machines. Information Processing Letters\u00a059, 203\u2013206 (1996)","journal-title":"Information Processing Letters"},{"key":"39_CR12","first-page":"306","volume-title":"Algorithms, Software, Architecture, Proceedings of the IFIP 12th World Computer Congress","author":"J. Wiedermann","year":"1992","unstructured":"Wiedermann, J.: Optimal algorithms for sorting on single-tape Turing machines. In: van Leeuwen, J. (ed.) Algorithms, Software, Architecture, Proceedings of the IFIP 12th World Computer Congress, Madrid, Spain, vol.\u00a0I, pp. 306\u2013314. Elsevier Science Publishers, Amsterdam (1992)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-88282-4_39.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T12:00:12Z","timestamp":1619524812000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-88282-4_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540882817","9783540882824"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-88282-4_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}