{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:49:18Z","timestamp":1773276558825,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[1994,8,1]],"date-time":"1994-08-01T00:00:00Z","timestamp":775699200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1994,8]]},"DOI":"10.1007\/bf01178735","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T16:52:44Z","timestamp":1108659164000},"page":"775-792","source":"Crossref","is-referenced-by-count":22,"title":["The path length of random skip lists"],"prefix":"10.1007","volume":"31","author":[{"given":"Peter","family":"Kirschenhofer","sequence":"first","affiliation":[]},{"given":"Helmut","family":"Prodinger","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1214\/aoap\/1177005651","volume":"2","author":"L. Devroye","year":"1992","unstructured":"Devroye, L.: A limit theory for random skip lists. Ann. Appl. Probab2, 597?609 (1992)","journal-title":"Ann. Appl. Probab"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1002\/rsa.3240030309","volume":"3","author":"P. Flajolet","year":"1992","unstructured":"Flajolet, P., Richmond, L.B.: Generalized digital trees and their difference-differential equations. Random Structures and Algorithms3, 305?320 (1992)","journal-title":"Random Structures and Algorithms"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1137\/0215054","volume":"15","author":"P. Flajolet","year":"1986","unstructured":"Flajolet, P., Sedgewick, R.: Digital search trees revisited. SIAM J. Comput15, 748?767 (1986)","journal-title":"SIAM J. Comput"},{"key":"CR4","first-page":"431","volume-title":"Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity","author":"P. Flajolet","year":"1990","unstructured":"Flajolet, P., Vitter, J.: Average-case analysis of algorithms and data structures. Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, pp. 431?542. Amsterdam: North-Holland 1990"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"Kirschenhofer, P., Prodinger, H.: A result in order statistics related to probabilistic counting. (Submitted, 1992)","DOI":"10.1007\/BF02243826"},{"key":"CR6","series-title":"Lect. Notes Math.","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/BFb0078599","volume-title":"Zahlentheoretische Analysis II","author":"P. Kirschenhofer","year":"1987","unstructured":"Kirschenhofer, P., Prodinger, H., Schoi\u00dfengeier, J.: Zur Auswertung gewisser numerischer Reihen mit Hilfe modularer Funktionen. In: Hlawka, E. (ed.), Zahlentheoretische Analysis II (Lect. Notes Math.1262, 108?110) Berlin, Heidelberg, New York: Springer 1987"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0166-218X(89)90050-4","volume":"25","author":"P. Kirschenhofer","year":"1989","unstructured":"Kirschenhofer, P., Prodinger, H., Szpankowski, W.: On the variance of the external pathlength in a symmetric digital trie. Discrete Appl. Math.25, 129?143 (1989)","journal-title":"Discrete Appl. Math."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(89)90115-1","volume":"68","author":"P. Kirschenhofer","year":"1989","unstructured":"Kirschenhofer, P., Prodinger, H., Szpankowski, W.: On the balance property of Patricia tries: external pathlength view. Theor. Comput. Sci.68, 1?17 (1989)","journal-title":"Theor. Comput. Sci."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"Kirschenhofer, P., Prodinger, H., Szpankowski, W.: Digital search trees again revisited: the internal path length perspective. SIAM J. Comput. (to appear)","DOI":"10.1137\/S0097539790189368"},{"issue":"42","key":"CR10","first-page":"267","volume":"22","author":"P. Kirschenhofer","year":"1987","unstructured":"Kirschenhofer, P., Prodinger, H., Tichy, R.F.: A contribution to the analysis of in situ permutation. Glasnik Mathematicki22(42), 267?278 (1987)","journal-title":"Glasnik Mathematicki"},{"key":"CR11","volume-title":"The art of computer programming, vol. 1","author":"D.E. Knuth","year":"1968","unstructured":"Knuth, D.E.: The art of computer programming, vol. 1, Reading, MA: Addison-Wesley 1968"},{"key":"CR12","volume-title":"The art of computer programming, vol. 3","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The art of computer programming, vol. 3. Reading, MA: Addison-Wesley 1973"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/BF01994884","volume":"32","author":"T. Papadakis","year":"1992","unstructured":"Papadakis, T., Munro I., Poblete, P.: Average search and update costs in skip lists. BIT32, 316?332 (1992)","journal-title":"BIT"},{"key":"CR14","unstructured":"Prodinger, H.: Combinatorics of geometrically distributed random variables: Left-to-right maxima. (Submitted 1992)"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W. Pugh","year":"1990","unstructured":"Pugh, W.: Skip lists: a probabilistic alternative to balanced trees. Commun. ACM33, 668?676 (1990)","journal-title":"Commun. ACM"},{"key":"CR16","first-page":"125","volume-title":"Probability Theory and Computer Science","author":"R. Sedgewick","year":"1983","unstructured":"Sedgewick, R.: Mathematical analysis of combinatorial algorithms. In: Louchard, G., Latouche, G. (eds.), Probability Theory and Computer Science, pp. 125?205. New York: Academic Press 1983"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/BF02241658","volume":"43","author":"W. Szpankowski","year":"1990","unstructured":"Szpankowski, W., Rego, V.: Yet another application of a binomial recurrence: order statistics. Computing43, 401?410 (1990)","journal-title":"Computing"},{"key":"CR18","volume-title":"A course in modern analysis","author":"E.T. Whittaker","year":"1927","unstructured":"Whittaker, E.T., Watson, G.N.: A course in modern analysis. Cambridge: Cambridge University Press 1927"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01178735.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01178735\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01178735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T20:22:22Z","timestamp":1586118142000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01178735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,8]]},"references-count":18,"journal-issue":{"issue":"8","published-print":{"date-parts":[[1994,8]]}},"alternative-id":["BF01178735"],"URL":"https:\/\/doi.org\/10.1007\/bf01178735","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,8]]}}}