{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T01:43:00Z","timestamp":1725500580535},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540775652"},{"type":"electronic","value":"9783540775669"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77566-9_35","type":"book-chapter","created":{"date-parts":[[2008,1,5]],"date-time":"2008-01-05T01:18:43Z","timestamp":1199495923000},"page":"406-417","source":"Crossref","is-referenced-by-count":1,"title":["Element Distinctness and Sorting on One-Tape Off-Line Turing Machines"],"prefix":"10.1007","author":[{"given":"Holger","family":"Petersen","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"35_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":"35_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01705890","volume":"4","author":"R.V. Book","year":"1970","unstructured":"Book, R.V., Greibach, S.: Quasi realtime languages. Mathematical Systems Theory\u00a04, 97\u2013111 (1970)","journal-title":"Mathematical Systems Theory"},{"key":"35_CR3","doi-asserted-by":"publisher","first-page":"1324","DOI":"10.1137\/S0097539702402780","volume":"34","author":"H. Buhrman","year":"2005","unstructured":"Buhrman, H., D\u00fcrr, C., Heiligman, M., H\u00f8yer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum algorithms for element distinctness. SIAM Journal on Computing\u00a034, 1324\u20131330 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"35_CR4","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":"35_CR5","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":"35_CR6","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(86)90150-7","volume":"47","author":"M. Karchmer","year":"1986","unstructured":"Karchmer, M.: Two time-space tradeoffs for element distinctness. Theoretical Computer Science\u00a047, 237\u2013246 (1986)","journal-title":"Theoretical Computer Science"},{"key":"35_CR7","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"35_CR8","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":"35_CR9","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":"35_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":"35_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":"35_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","SOFSEM 2008: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77566-9_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:44:58Z","timestamp":1619505898000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77566-9_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540775652","9783540775669"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77566-9_35","relation":{},"subject":[]}}