{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T08:42:48Z","timestamp":1770280968251,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540515425","type":"print"},{"value":"9783540482376","type":"electronic"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"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":[[1989]]},"DOI":"10.1007\/3-540-51542-9_8","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:08:06Z","timestamp":1330186086000},"page":"67-74","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Fully persistent arrays"],"prefix":"10.1007","author":[{"given":"Paul F.","family":"Dietz","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Paul F. Dietz. Maintaining order in a linked list. In Proc. 14th ACM STOC, pages 122\u2013127, May 1982.","DOI":"10.1145\/800070.802184"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Paul F. Dietz and Daniel D. Sleator. Two algorithms for maintaining order in a list. In Proc. 19th ACM STOC, pages 365\u2013372, May 1987. Submitted to JCSS. A revised version of the paper is available that tightens up the analysis.","DOI":"10.1145\/28395.28434"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, A. Karlin, K. Melhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. In Proc. 29th FOCS, pages 524\u2013531, 1988. The application to persistent arrays was presented but does not appear in the proceedings.","DOI":"10.1109\/SFCS.1988.21968"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. In Proc. 18th ACM STOC, pages 109\u2013121, May 1986.","DOI":"10.1145\/12130.12142"},{"key":"8_CR5","first-page":"85","volume":"10","author":"C. Montangero","year":"1978","unstructured":"Carlo Montangero, Giuliano Pacini, Maria Simi, and Franco Turini. Information management in context trees. Acta. Info., 10:85\u201394, 1978.","journal-title":"Acta. Info."},{"key":"8_CR6","unstructured":"Mark Overmars. A O(1) average time update scheme for balanced binary search trees. Bull. EATCS, pages 27\u201329, 1982."},{"issue":"7","key":"8_CR7","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"Neil Sarnak and Robert E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29(7):669\u2013679, July 1986.","journal-title":"Communications of the ACM"},{"issue":"1","key":"8_CR8","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF00289142","volume":"21","author":"A. K. Tsakalidis","year":"1984","unstructured":"A. K. Tsakalidis. Maintaining order in a generalized linked list. Acta. Info., 21(1):101\u2013112, 1984.","journal-title":"Acta. Info."},{"issue":"3","key":"8_CR9","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Info. Proc. Lett., 6(3):80\u201382, June 1977.","journal-title":"Info. Proc. Lett."},{"key":"8_CR10","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Math. Sys. Theo., 10:99\u2013127, 1977.","journal-title":"Math. Sys. Theo."},{"issue":"4","key":"8_CR11","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(75)90046-0","volume":"3","author":"B. Wegbreit","year":"1975","unstructured":"Ben Wegbreit. Retrieval from context trees. Info. Proc. Lett., 3(4):119\u2013120, March 1975.","journal-title":"Info. Proc. Lett."},{"issue":"9","key":"8_CR12","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1145\/360336.360347","volume":"19","author":"B. Wegbreit","year":"1976","unstructured":"Ben Wegbreit. Faster retrieval from context trees. Communications of the ACM, 19(9):526\u2013529, September 1976.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51542-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T19:02:16Z","timestamp":1578510136000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51542-9_8"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540515425","9783540482376"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-51542-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"26 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}