{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T01:23:03Z","timestamp":1697160183432},"reference-count":39,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2002,7,1]],"date-time":"2002-07-01T00:00:00Z","timestamp":1025481600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Algorithms"],"published-print":{"date-parts":[[2002,7]]},"DOI":"10.1016\/s0196-6774(02)00212-2","type":"journal-article","created":{"date-parts":[[2002,10,8]],"date-time":"2002-10-08T19:37:24Z","timestamp":1034105844000},"page":"63-97","source":"Crossref","is-referenced-by-count":7,"title":["Limit laws for the height in PATRICIA tries"],"prefix":"10.1016","volume":"44","author":[{"given":"Charles","family":"Knessl","sequence":"first","affiliation":[]},{"given":"Wojciech","family":"Szpankowski","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0196-6774(02)00212-2_BIB001","series-title":"Handbook of Mathematical Functions","year":"1962"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB002","series-title":"Advanced Mathematical Methods for Scientists and Engineers","author":"Bender","year":"1978"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB003","series-title":"Asymptotic Expansions of Integrals","author":"Bleistein","year":"1986"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB004","doi-asserted-by":"crossref","first-page":"RR6","DOI":"10.37236\/1321","article-title":"From recursions to asymptotics: On Szekeres' formula for the number of partitions","volume":"4","author":"Canfield","year":"1997","journal-title":"Electron. J. Combin."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB005","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF00264248","article-title":"A probabilistic analysis of the height of tries and the complexity of trie sort","volume":"21","author":"Devroye","year":"1984","journal-title":"Acta Inform."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB006","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1002\/rsa.3240030209","article-title":"A note on the probabilistic analysis of patricia tries","volume":"3","author":"Devroye","year":"1992","journal-title":"Random Structures Algorithms"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB007","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1214\/aoap\/1177005709","article-title":"A study of trie-like structures under the density model","volume":"2","author":"Devroye","year":"1992","journal-title":"Ann. Appl. Probab."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB008","doi-asserted-by":"crossref","first-page":"373","DOI":"10.2307\/2324917","article-title":"A pseudorandom sequence\u2014How random is it?","volume":"99","author":"Ehrenfeucht","year":"1992","journal-title":"Amer. Math. Monthly"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB009","series-title":"Analysis I: Integral Representations and Asymptotic Methods","article-title":"Asymptotic methods in analysis","author":"Fedoryuk","year":"1989"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB010","doi-asserted-by":"crossref","first-page":"1260","DOI":"10.1214\/aoap\/1035463332","article-title":"On the distribution for the duration of a randomized leader election algorithm","volume":"6","author":"Fill","year":"1996","journal-title":"Ann. Appl. Probab."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB011","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF00264279","article-title":"On the performance evaluation of extendible hashing and trie searching","volume":"20","author":"Flajolet","year":"1983","journal-title":"Acta Inform."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB012","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(95)00002-E","article-title":"Mellin transforms and asymptotics: Harmonic sums","volume":"144","author":"Flajolet","year":"1995","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB013","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/PL00009207","article-title":"Greedy algorithms for the shortest common superstring problem that are asymptotically optimal","volume":"21","author":"Frieze","year":"1998","journal-title":"Algorithmica"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB014","series-title":"JWKB Approximation","author":"Froman","year":"1965"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB015","series-title":"Algorithms on Strings, Trees, and Sequences","author":"Gusfield","year":"1997"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB016","series-title":"Trie Partitioning Process: Limiting Distributions","volume":"214","author":"Jacquet","year":"1986"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB017","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0304-3975(94)00298-W","article-title":"Asymptotic behavior of the Lempel\u2013Ziv parsing scheme and digital search trees","volume":"144","author":"Jacquet","year":"1995","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"10.1016\/S0196-6774(02)00212-2_BIB018","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00167-9","article-title":"Analytic depoissonization and its applications","volume":"201","author":"Jacquet","year":"1998","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB019","doi-asserted-by":"crossref","first-page":"1462","DOI":"10.1109\/TIT.2002.1003834","article-title":"A universal predictor based on pattern matching","volume":"48","author":"Jacquet","year":"2002","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB020","series-title":"Sorting and Searching","volume":"3","author":"Knuth","year":"1998"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB021","first-page":"43","article-title":"Quicksort algorithm again revisited","volume":"3","author":"Knessl","year":"1999","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB022","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1137\/S0097539799356812","article-title":"Asymptotic behavior of the height in a digital search tree and the longest phrase of the Lempel\u2013Ziv scheme","volume":"30","author":"Knessl","year":"2000","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB023","doi-asserted-by":"crossref","first-page":"R39","DOI":"10.37236\/1517","article-title":"A note on the asymptotic behavior of the height in b-tries for b large","volume":"7","author":"Knessl","year":"2000","journal-title":"Electron. J. Combin."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB024","series-title":"Matched Asymptotic Expansions: Ideas and Techniques","author":"Lagerstrom","year":"1988"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB025","series-title":"Evolution of Random Search Trees","author":"Mahmoud","year":"1992"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB026","series-title":"Introduction to Perturbation Techniques","author":"Nayfeh","year":"1981"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB027","first-page":"1063","article-title":"Asymptotic Enumeration","volume":"II","author":"Odlyzko","year":"1995"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB028","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1214\/aop\/1176993000","article-title":"Asymptotic growth of a class of random trees","volume":"13","author":"Pittel","year":"1985","journal-title":"Ann. Probab."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB029","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/1427240","article-title":"Path in a random digital tree: limiting distributions","volume":"18","author":"Pittel","year":"1986","journal-title":"Adv. Appl. Prob."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB030","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1016\/0097-3165(90)90072-5","article-title":"How many random questions are necessary to identify n distinct objects?","volume":"55","author":"Pittel","year":"1990","journal-title":"J. Combin. Theory Ser. A"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB031","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/0020-0190(81)90033-8","article-title":"On the average height of trees in digital searching and dynamic hashing","volume":"13","author":"R\u00e9gnier","year":"1981","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB032","first-page":"355","article-title":"On random subsets of a finite set","volume":"3","author":"R\u00e9nyi","year":"1961","journal-title":"Mathematica (Cluj)"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB033","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1145\/96559.214080","article-title":"Patricia tries again revisited","volume":"37","author":"Szpankowski","year":"1990","journal-title":"J. ACM"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB034","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/BF01759045","article-title":"On the height of digital trees and related problems","volume":"6","author":"Szpankowski","year":"1991","journal-title":"Algorithmica"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB035","doi-asserted-by":"crossref","first-page":"1176","DOI":"10.1137\/0222070","article-title":"A generalized suffix tree and its (un)expected asymptotic behaviors","volume":"22","author":"Szpankowski","year":"1993","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0196-6774(02)00212-2_BIB036","series-title":"Average Case Analysis of Algorithms on Sequences","author":"Szpankowski","year":"2001"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB037","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/0020-0190(80)90008-3","article-title":"A note on the analysis of extendible hashing","volume":"11","author":"Yao","year":"1980","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"10.1016\/S0196-6774(02)00212-2_BIB038","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/S0196-6774(02)00212-2_BIB039","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677402002122?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677402002122?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,8]],"date-time":"2020-03-08T06:58:54Z","timestamp":1583650734000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0196677402002122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,7]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,7]]}},"alternative-id":["S0196677402002122"],"URL":"https:\/\/doi.org\/10.1016\/s0196-6774(02)00212-2","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[2002,7]]}}}