{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:52Z","timestamp":1725663772453},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571551"},{"type":"electronic","value":"9783540479185"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57155-8_256","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T07:06:04Z","timestamp":1330239964000},"page":"289-301","source":"Crossref","is-referenced-by-count":1,"title":["Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract)"],"prefix":"10.1007","author":[{"given":"Paul F.","family":"Dietz","sequence":"first","affiliation":[]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"28_CR1","first-page":"217","volume":"63","author":"M. Ajtai","year":"1984","unstructured":"M. Ajtai, M. Fredman, and J. Koml\u00f3s. Hash functions for priority queues. I & C, 63 (1984), pp. 217\u2013225.","journal-title":"I & C"},{"key":"28_CR2","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1145\/359460.359470","volume":"21","author":"H. Baker","year":"1978","unstructured":"H. Baker. List processing in real time on a serial computer. CACM, 21 (1978), pp. 280\u2013294.","journal-title":"CACM"},{"key":"28_CR3","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1137\/0215072","volume":"15","author":"N. Blum","year":"1986","unstructured":"N. Blum. On the single-operation worst-case time complexity of the disjoint set union problem. SICOMP, 15 (1986), pp. 1021\u20131024.","journal-title":"SICOMP"},{"key":"28_CR4","unstructured":"A. Buchsbaum. Personal communication."},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"P. F. Dietz. Maintaining order in a linked list. In Proc. 14th STOC (1982), pp. 122\u2013127.","DOI":"10.1145\/800070.802184"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"P. F. Dietz. Fully persistent arrays. In Proc. WADS 89 (1989), LNCS 382, pp. 67\u201374.","DOI":"10.1007\/3-540-51542-9_8"},{"key":"28_CR7","unstructured":"P. F. Dietz. Monotonie list labeling with good worst case performance. manuscript, February 1991."},{"key":"28_CR8","unstructured":"P. F. Dietz and R. Raman. Persistence, amortization and randomization. In Proc. 2nd SODA (1991), pp. 77\u201387. Revised version, Univ. of Rochester CS TR 353, 1991."},{"key":"28_CR9","unstructured":"P. F. Dietz and R. Raman. On some combinatorial games and their applications. Univ. of Rochester CS TR 392, 1991."},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"P. F. Dietz and D. D. Sleator. Two algorithms for maintaining order in a list. In Proc. 19th STOC (1987), pp. 365\u2013372.","DOI":"10.1145\/28395.28434"},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnhert and R. E. Tarjan. Dynamic perfect hashing: upper and lower bounds. In Proc. 29th FOCS (1988), pp. 524\u2013531.","DOI":"10.1109\/SFCS.1988.21968"},{"key":"28_CR12","doi-asserted-by":"crossref","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"31","author":"J. R. Driscoll","year":"1988","unstructured":"J. R. Driscoll, H. N. Gabow, R. Shrairman and R. E. Tarjan. Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation. CACM 31 (1988), pp. 1343\u20131354.","journal-title":"CACM"},{"key":"28_CR13","first-page":"86","volume":"38","author":"J. R. Driscoll","year":"1989","unstructured":"J. R. Driscoll, N. Sarnak, D. D. Sleator and R. E. Tarjan. Making data structures persistent. JCSS, 38 (1989), pp. 86\u2013124.","journal-title":"JCSS"},{"key":"28_CR14","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1145\/321724.321726","volume":"19","author":"M. Fischer","year":"1972","unstructured":"M. Fischer, A. Meyer and A. Rosenberg. Real-time simulation of multihead tape units. JACM, 19 (1972), pp. 590\u2013607.","journal-title":"JACM"},{"key":"28_CR15","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1145\/322234.322244","volume":"28","author":"Z. Galil","year":"1981","unstructured":"Z. Galil. String matching in real time. JACM, 28 (1981), 134\u2013149.","journal-title":"JACM"},{"key":"28_CR16","unstructured":"J. Gil, Y. Matias and U. Vishkin. Towards a theory of nearly constant-time parallel algorithms. In Proc. 32nd, FOCS (1991), pp. 698\u2013710."},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"M. T. Goodrich and S. R. Kosaraju. Sorting on a parallel pointer machine with applications to set expression evaluation. In Proc. 30th FOCS (1989), pp. 190\u2013196.","DOI":"10.1109\/SFCS.1989.63477"},{"key":"28_CR18","unstructured":"T. Hagerup. Fast parallel space allocation, estimation and integer sorting. TR MPI-I-91-106, MPI f\u00fcr Informatik, 1991. Preliminary version in Proc. 23rd STOC, 1991."},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"G. F. Italiano and N. Sarnak. Fully persistent data structures for disjoint set union problems. Proc. WADS '91 (1991), LNCS 519, pp. 449\u2013460.","DOI":"10.1007\/BFb0028283"},{"key":"28_CR20","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1145\/322234.322246","volume":"28","author":"B. Leong","year":"1981","unstructured":"B. Leong and J. I. Seiferas. New real-time simulations of multihead tape units. JACM, 28 (1981), pp. 166\u2013180.","journal-title":"JACM"},{"key":"28_CR21","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF00299635","volume":"26","author":"C. Levcopolous","year":"1988","unstructured":"C. Levcopolous and M. H. Overmars. A balanced search tree with O(1) worst-case update time. Acta Inf., 26, (1988), pp. 269\u2013278.","journal-title":"Acta Inf."},{"key":"28_CR22","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01840386","volume":"5","author":"K. Mehlhorn","year":"1990","unstructured":"K. Mehlhorn and S. N\u00e4her. Dynamic fractional cascading. Algorithmica, 5 (1990), pp. 215\u2013241.","journal-title":"Algorithmica"},{"key":"28_CR23","volume-title":"LNCS 156","author":"M. H. Overmars","year":"1983","unstructured":"M. H. Overmars. The design of dynamic data structures, LNCS 156, Springer-Verlag, Berlin, 1983."},{"key":"28_CR24","unstructured":"P. Raghavan. Lecture notes in randomized algorithms. TR RC 15340, IBM, 1989."},{"key":"28_CR25","unstructured":"R. Raman. Eliminating amortization: on data structures with guaranteed response time. PhD thesis, U. of Rochester, 1991."},{"key":"28_CR26","unstructured":"N. Sarnak. Persistent data structures. PhD thesis, New York Univ., 1986."},{"key":"28_CR27","doi-asserted-by":"crossref","unstructured":"S. Sen. Fractional cascading revisited. In Proc. SWAT '92 (1992), LNCS 621, pp. 212\u2013220.","DOI":"10.1007\/3-540-55706-7_18"},{"key":"28_CR28","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 Inf., 21 (1984), pp. 101\u2013112.","journal-title":"Acta Inf."},{"key":"28_CR29","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Boas van Emde","year":"1977","unstructured":"P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. IPL, 6 (1977), pp. 80\u201382.","journal-title":"IPL"},{"key":"28_CR30","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1145\/360336.360338","volume":"19","author":"P. Wadler","year":"1976","unstructured":"P. Wadler. Analysis of an algorithm for real-time garbage collection. CACM, 19 (1976), pp. 491\u2013500.","journal-title":"CACM"},{"key":"28_CR31","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1145\/3828.3839","volume":"32","author":"D. E. Willard","year":"1985","unstructured":"D. E. Willard and G. S. Lueker. Adding range restriction capability to dynamic data structures. JACM, 32 (1985), pp. 597\u2013617.","journal-title":"JACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57155-8_256.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:08:18Z","timestamp":1605629298000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57155-8_256"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571551","9783540479185"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-57155-8_256","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}