{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T01:48:01Z","timestamp":1774489681773,"version":"3.50.1"},"reference-count":65,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2001,2,1]],"date-time":"2001-02-01T00:00:00Z","timestamp":980985600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2001,2]]},"DOI":"10.1007\/bf02679623","type":"journal-article","created":{"date-parts":[[2007,7,29]],"date-time":"2007-07-29T04:42:49Z","timestamp":1185684169000},"page":"307-369","source":"Crossref","is-referenced-by-count":57,"title":["Dynamical sources in information theory: A general analysis of trie structures"],"prefix":"10.1007","volume":"29","author":[{"given":"J.","family":"Cl\u00e9ment","sequence":"first","affiliation":[]},{"given":"P.","family":"Flajolet","sequence":"additional","affiliation":[]},{"given":"B.","family":"Vall\u00e9e","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"BF02679623_CR1","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1145\/322092.322094","volume":"25","author":"B. Allen","year":"1978","unstructured":"Allen, B., and Munro, I. Self-organizing binary search trees.Journal of the ACM 25(4) (Oct. 1978), 526\u2013535.","journal-title":"Journal of the ACM"},{"key":"BF02679623_CR2","volume-title":"Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces","author":"T. Bedford","year":"1991","unstructured":"Bedford, T., Keane, M., and Series, C.Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces. Oxford University Press, Oxford, 1991."},{"key":"BF02679623_CR3","first-page":"360","volume-title":"Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"J. Bentley","year":"1997","unstructured":"Bentley, J., and Sedgewick, R. Fast algorithms for sorting and searching strings. InProceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, January 1997), pp. 360\u2013369. SIAM Press, Philadelphia, PA, 1997."},{"key":"BF02679623_CR4","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0167-2789(93)90199-B","volume":"67","author":"E.B. Bogomolny","year":"1993","unstructured":"Bogomolny, E.B., and Carioli, M. Quantum maps from transfer operators.Physica D 67 (1993), 88\u2013112.","journal-title":"Physica D"},{"issue":"3","key":"BF02679623_CR5","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1145\/321958.321965","volume":"23","author":"W. H. Burge","year":"1976","unstructured":"Burge, W. H. An analysis of binary search trees formed from sequences of nondistinct keys.Journal of the ACM 23(3) (July 1976), 451\u2013454.","journal-title":"Journal of the ACM"},{"issue":"3","key":"BF02679623_CR6","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1145\/363958.363987","volume":"7","author":"H. A. Clampett","year":"1964","unstructured":"Clampett, H. A. Randomized binary searching with tree structures.Communications of the ACM 7(3) (March 1964), 163\u2013165.","journal-title":"Communications of the ACM"},{"key":"BF02679623_CR7","first-page":"531","volume-title":"Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"J. Cl\u00e9ment","year":"1988","unstructured":"Cl\u00e9ment, J., Flajolet, P., and Vall\u00e9e, B. The analysis of hybrid trie structures. InProceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (Philadelphia, 1998), pp. 531\u2013539. SIAM Press, Philadelphia, PA, 1988."},{"key":"BF02679623_CR8","unstructured":"Cl\u00e9ment, J., and Zimmermann, P. An efficient spell-checker based on ternary search tries (provisional title). Research report, Institut National de Recherche en Informatique et en Automatique, 2000. In preparation."},{"key":"BF02679623_CR9","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1017\/S0963548397003258","volume":"6","author":"H. Daud\u00e9","year":"1997","unstructured":"Daud\u00e9, H., Flajolet, P., and Vall\u00e9e, B. An average-case analysis of the Gaussian algorithm for lattice reduction.Combinatorics, Probability and Computing 6 (1997), 397\u2013433.","journal-title":"Combinatorics, Probability and Computing"},{"key":"BF02679623_CR10","volume-title":"Asymptotic Methods in Analysis","author":"N. G. Bruijn De","year":"1970","unstructured":"De Bruijn, N. G.Asymptotic Methods in Analysis. Dover, 1981. first edition, A reprint of the third North-Holland edition, Amsterdam, 1970 (1958).","edition":"first edition"},{"key":"BF02679623_CR11","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF00264248","volume":"21","author":"L. Devroye","year":"1984","unstructured":"Devroye, L. A probabilistic analysis of the height of tries and of the complexity of triesort.Acta Informatica 21 (1984), 229\u2013237.","journal-title":"Acta Informatica"},{"issue":"2","key":"BF02679623_CR12","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1214\/aoap\/1177005709","volume":"2","author":"L. Devroye","year":"1992","unstructured":"Devroye, L. A study of trie-like structures under the density model.The Annals of Applied Probability 2(2) (1992), 402\u2013434.","journal-title":"The Annals of Applied Probability"},{"key":"BF02679623_CR13","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BF01232667","volume":"114","author":"I. Efrat","year":"1993","unstructured":"Efrat, I. Dynamics of the continued fraction map and the spectral theory ofSL(2,Z).Inventiones Mathematicae 114 (1993), 207\u2013218.","journal-title":"Inventiones Mathematicae"},{"key":"BF02679623_CR14","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1145\/320083.320092","volume":"4","author":"R. Fagin","year":"1979","unstructured":"Fagin, R., Nievergelt, J., Pippenger, N., and Strong, R. Extendible hashing: a fast access method for dynamic files.ACM Transactions on Database Systems 4 (1979), 315\u2013344.","journal-title":"ACM Transactions on Database Systems"},{"issue":"1","key":"BF02679623_CR15","doi-asserted-by":"crossref","first-page":"13","DOI":"10.4064\/aa-61-1-13-34","volume":"61","author":"C. Faivre","year":"1992","unstructured":"Faivre, C. Distribution of L\u00e9vy\u2019s constants for quadratic numbers.Acta Arithmetica 61(1) (1992), 13\u201334.","journal-title":"Acta Arithmetica"},{"key":"BF02679623_CR16","doi-asserted-by":"crossref","first-page":"441","DOI":"10.2307\/1427308","volume":"18","author":"G. Fayolle","year":"1986","unstructured":"Fayolle, G., Flajolet, P., and Hofri, M. On a functional equation arising in the analysis of a protocol for a multi-accessbroadcast channel.Advances in Applied Probability 18 (1986), 441\u2013472.","journal-title":"Advances in Applied Probability"},{"key":"BF02679623_CR17","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF00264279","volume":"20","author":"P. Flajolet","year":"1983","unstructured":"Flajolet, P. On the performance evaluation of extendible hashing and trie searching.Acta Informatica 20 (1983), 345\u2013369.","journal-title":"Acta Informatica"},{"key":"BF02679623_CR18","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0166-218X(92)90177-C","volume":"39","author":"P. Flajolet","year":"1992","unstructured":"Flajolet, P., Gardy, D., and Thimonier, L. Birthday paradox, coupon collectors, caching algorithms, and self-organizing search.Discrete Applied Mathematics 39 (1992), 207\u2013229.","journal-title":"Discrete Applied Mathematics"},{"issue":"1\u20132","key":"BF02679623_CR19","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(95)00002-E","volume":"144","author":"P. Flajolet","year":"1995","unstructured":"Flajolet, P., Gourdon, X., and Dumas, P. Mellin transforms and asymptotics: harmonic sums.Theoretical Computer Science 144(1\u20132) (June 1995), 3\u201358.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"BF02679623_CR20","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1145\/5383.5453","volume":"33","author":"P. Flajolet","year":"1986","unstructured":"Flajolet, P., and Puech, C. Partial match retrieval of multidimensional data.Journal of the ACM 33(2) (1986), 371\u2013407.","journal-title":"Journal of the ACM"},{"key":"BF02679623_CR21","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BFb0012773","volume-title":"Automata, Languages and Programming","author":"P. Flajolet","year":"1982","unstructured":"Flajolet, P., and Steyaert, J.-M. A branching process arising in dynamic hashing, trie searching and polynomial factorization. InAutomata, Languages and Programming, M. Nielsen and E. M. Schmidt, eds., vol. 140 of Lecture Notes in Computer Science, pp. 239\u2013251. Springer-Verlag, Berlin, 1982. Proceedings of 9th ICALP Colloquium, Aarhus, Denmark, July 1982."},{"key":"BF02679623_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00123-0","volume":"194","author":"P. Flajolet","year":"1998","unstructured":"Flajolet, P., and Vall\u00e9e, B. Continued fraction algorithms, functional operators and structure constants.Theoretical Computer Science 194 (1998), 1\u201334.","journal-title":"Theoretical Computer Science"},{"key":"BF02679623_CR23","volume-title":"Handbook of Algorithms and Data Structures: in Pascal and C","author":"G. H. Gonnet","year":"1991","unstructured":"Gonnet, G. H., and Baeza-Yates, R.Handbook of Algorithms and Data Structures: in Pascal and C, second edn. Addison-Wesley, Reading, MA, 1991.","edition":"second edn."},{"key":"BF02679623_CR24","volume-title":"Produits tensoriels topologiques et espaces nucl\u00e9aires","author":"A. Grothendieck","year":"1955","unstructured":"Grothendieck, A.Produits tensoriels topologiques et espaces nucl\u00e9aires. No. 16 in Memoirs of the American Mathematical Society. A.M.S., Providence, RI, 1955."},{"key":"BF02679623_CR25","doi-asserted-by":"crossref","first-page":"319","DOI":"10.24033\/bsmf.1476","volume":"84","author":"A. Grothendieck","year":"1956","unstructured":"Grothendieck, A. La th\u00e9orie de Fredholm.Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France 84 (1956), 319\u2013384.","journal-title":"Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France"},{"key":"BF02679623_CR26","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/BFb0022669","volume-title":"CAAP \u201986","author":"P. Jacquet","year":"1986","unstructured":"Jacquet, P., and R\u00e9gnier, M. Trie partitioning process: limiting distributions. InCAAP \u201986, P. Franchi-Zanetacchi, ed., vol. 214 of Lecture Notes in Computer Science, pp. 196\u2013210. Springer-Verlag, Berlin, 1986. Proceedings of the 11th Colloquium on Trees in Algebra and Programming, Nice France, March 1986."},{"issue":"5","key":"BF02679623_CR27","doi-asserted-by":"crossref","first-page":"1470","DOI":"10.1109\/18.133271","volume":"37","author":"P. Jacquet","year":"1991","unstructured":"Jacquet, P., and Szpankowski, W. Analysis of digital tries with Markovian dependency.IEEE Transactions on Information Theory 37(5) (1991), 1470\u20131475.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"2","key":"BF02679623_CR28","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0097-3165(94)90065-5","volume":"66","author":"P. Jacquet","year":"1994","unstructured":"Jacquet, P., and Szpankowski, W. Autocorrelation on words and its applications: analysis of suffix trees by string-ruler approach.Journal of Combinatorial Theory. Series A 66(2) (1994), 237\u2013269.","journal-title":"Journal of Combinatorial Theory. Series A"},{"issue":"1\u20132","key":"BF02679623_CR29","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0304-3975(94)00298-W","volume":"144","author":"P. Jacquet","year":"1995","unstructured":"Jacquet, P., and Szpankowski, W. Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees.Theoretical Computer Science 144(1\u20132) (1995), 161\u2013197.","journal-title":"Theoretical Computer Science"},{"issue":"1\u20132","key":"BF02679623_CR30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00167-9","volume":"201","author":"P. Jacquet","year":"1998","unstructured":"Jacquet, P., and Szpankowski, W. Analytical de-Poissonization and its applications.Theoretical Computer Science 201(1\u20132) (1998), 1\u201362.","journal-title":"Theoretical Computer Science"},{"key":"BF02679623_CR31","unstructured":"Janson, S. Private communication."},{"key":"BF02679623_CR32","volume-title":"Perturbation Theory for Linear Operators","author":"T. Kato","year":"1980","unstructured":"Kato, T.Perturbation Theory for Linear Operators. Springer-Verlag, New York, 1980."},{"key":"BF02679623_CR33","first-page":"339","volume":"197","author":"P. Kirschenhofer","year":"1988","unstructured":"Kirschenhofer, P., and Prodinger, H. Eine Anwendung der Theorie der Modulfunktionen in der Informatik.Sitzungsberichte der \u00d6sterreichischen Akademie der Wissenschaften 197 (1988), 339\u2013366.","journal-title":"Sitzungsberichte der \u00d6sterreichischen Akademie der Wissenschaften"},{"key":"BF02679623_CR34","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1112\/S0025579300006409","volume":"38","author":"P. Kirschenhofer","year":"1991","unstructured":"Kirschenhofer, P., and Prodinger, H. On some applications of formul\u00e6 of Ramanujan in the analysis of algorithms.Mathematika 38 (1991), 14\u201333.","journal-title":"Mathematika"},{"key":"BF02679623_CR35","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/(SICI)1098-2418(199612)9:4<379::AID-RSA3>3.0.CO;2-U","volume":"9","author":"P. Kirschenhofer","year":"1996","unstructured":"Kirschenhofer, P., Prodinger, H., and Szpankowski, W. Analysis of a splitting process arising in probabilistic counting and other related algorithms.Random Structures & Algorithms 9 (1996), 379\u2013402.","journal-title":"Random Structures & Algorithms"},{"key":"BF02679623_CR36","volume-title":"The Art of Computer Programming","author":"D. E. Knuth","year":"1998","unstructured":"Knuth, D. E.The Art of Computer Programming, third edn., vol. 3: Sorting and Searching. Addison-Wesley, Reading, MA, 1998.","edition":"third edn."},{"key":"BF02679623_CR37","volume-title":"Positive Solutions of Operator Equations","author":"M. Krasnoselskii","year":"1964","unstructured":"Krasnoselskii, M.Positive Solutions of Operator Equations. P. Noordhoff, Groningen, 1964."},{"key":"BF02679623_CR38","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/BF01931695","volume":"18","author":"P. A. Larson","year":"1978","unstructured":"Larson, P. A. Dynamic hashing.BIT 18 (1978), 184\u2013201.","journal-title":"BIT"},{"key":"BF02679623_CR39","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511626302","volume-title":"An Introduction to Symbolic Dynamics and Coding","author":"D. Lind","year":"1995","unstructured":"Lind, D., and Marcus, B.An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, 1995."},{"key":"BF02679623_CR40","volume-title":"Combinatorics on Words","author":"M. Lothaire","year":"1983","unstructured":"Lothaire, M.Combinatorics on Words, vol. 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, MA, 1983."},{"key":"BF02679623_CR41","volume-title":"Evolution of Random Search Trees","author":"H. Mahmoud","year":"1992","unstructured":"Mahmoud, H.Evolution of Random Search Trees. Wiley, New York, 1992."},{"key":"BF02679623_CR42","unstructured":"Mayer, D. H. Private communication."},{"key":"BF02679623_CR43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01562537","volume":"68","author":"D. H. Mayer","year":"1979","unstructured":"Mayer, D. H. Spectral properties of certain composition operators arising in statistical mechanics.Communications in Mathematical Physics 68 (1979), 1\u20138.","journal-title":"Communications in Mathematical Physics"},{"key":"BF02679623_CR44","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0022-1236(80)90004-X","volume":"35","author":"D. H. Mayer","year":"1980","unstructured":"Mayer, D. H. On composition operators on Banach spaces of holomorphic functions.Journal of Functional Analysis 35 (1980), 191\u2013206.","journal-title":"Journal of Functional Analysis"},{"issue":"1","key":"BF02679623_CR45","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/1427240","volume":"18","author":"B. Pittel","year":"1986","unstructured":"Pittel, B. Paths in a random digital tree: limiting distributions.Advances in Applied Probability 18(1) (1986), 139\u2013155.","journal-title":"Advances in Applied Probability"},{"key":"BF02679623_CR46","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1017\/S0143385700002327","volume":"4","author":"M. Pollicott","year":"1984","unstructured":"Pollicott, M. A complex Ruelle-Perron-Frobenius theorem and two counterexamples.Ergodic Theory and Dynamical Systems 4 (1984), 135\u2013146.","journal-title":"Ergodic Theory and Dynamical Systems"},{"key":"BF02679623_CR47","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0012-365X(95)00141-I","volume":"153","author":"H. Prodinger","year":"1996","unstructured":"Prodinger, H. Combinatorics of geometrically distributed random variables: left-to-right maxima.Discrete Mathematics 153 (1996), 253\u2013270.","journal-title":"Discrete Mathematics"},{"key":"BF02679623_CR48","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/0020-0190(81)90033-8","volume":"13","author":"M. R\u00e9gnier","year":"1982","unstructured":"R\u00e9gnier, M. On the average height of trees in in digital search and dynamic hashing.Information Processing Letters 13 (1982), 64\u201366.","journal-title":"Information Processing Letters"},{"key":"BF02679623_CR49","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1137\/0205003","volume":"5","author":"R. L. Rivest","year":"1976","unstructured":"Rivest, R. L. Partial match retrieval algorithms.SIAM Journal on Computing 5 (1976), 19\u201350.","journal-title":"SIAM Journal on Computing"},{"key":"BF02679623_CR50","volume-title":"Thermodynamic Formalism","author":"D. Ruelle","year":"1978","unstructured":"Ruelle, D.Thermodynamic Formalism. Addison-Wesley, Reading, MA, 1978."},{"key":"BF02679623_CR51","volume-title":"Dynamical Zeta Functions for Piecewise Monotone Maps of the Interval","author":"D. Ruelle","year":"1994","unstructured":"Ruelle, D.Dynamical Zeta Functions for Piecewise Monotone Maps of the Interval, vol. 4 of CRM Monograph Series. American Mathematical Society, Providence, RI, 1994."},{"key":"BF02679623_CR52","unstructured":"Schwartz, H. Composition operators in \u210b p . Ph.D. thesis, University of Toledo, 1969."},{"key":"BF02679623_CR53","volume-title":"Algorithms in C: Fundamentals, Data Structures, Sorting, Searching","author":"R. Sedgewick","year":"1988","unstructured":"Sedgewick, R.Algorithms in C: Fundamentals, Data Structures, Sorting, Searching, third edn. Addison-Wesley, Reading, MA, 1988.","edition":"third edn."},{"key":"BF02679623_CR54","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1090\/S0002-9939-1987-0883400-9","volume":"100","author":"J. Shapiro","year":"1997","unstructured":"Shapiro, J. Compact composition operators on spaces of boundary regular holomorphic functions.Proceedings of the AMS 100 (1997), 49\u201357.","journal-title":"Proceedings of the AMS"},{"key":"BF02679623_CR55","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1512\/iumj.1974.23.23041","volume":"23","author":"J. Shapiro","year":"1973","unstructured":"Shapiro, J., and Taylor, P. Compact, nuclear, and Hilbert-Schmidt composition operators on \u210b2.Indiana University Mathematics Journal 23 (1973), 471\u2013496.","journal-title":"Indiana University Mathematics Journal"},{"key":"BF02679623_CR56","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/0196-6774(88)90039-9","volume":"9","author":"W. Szpankowski","year":"1988","unstructured":"Szpankowski, W. Some results onV-ary asymmetric tries.Journal of Algorithms 9 (1988), 224\u2013244.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"BF02679623_CR57","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/BF01759045","volume":"6","author":"W. Szpankowski","year":"1991","unstructured":"Szpankowski, W. On the height of digital trees and related problems.Algorithmica 6(2) (1991), 256\u2013277.","journal-title":"Algorithmica"},{"key":"BF02679623_CR58","volume-title":"The Theory of the Riemann Zeta-Function","author":"E. C. Titchmarsh","year":"1986","unstructured":"Titchmarsh, E. C., and Heath-Brown, D. R.The Theory of the Riemann Zeta-Function, second edn. Oxford Science Publications, Oxford, 1986.","edition":"second edn."},{"key":"BF02679623_CR59","unstructured":"Trabb Pardo, L. Set representation and set intersection. Technical report, Stanford University, 1978."},{"key":"BF02679623_CR60","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1007\/3-540-63397-9_37","volume-title":"Algorithms\u2014ESA \u201997","author":"B. Vall\u00e9e","year":"1997","unstructured":"Vall\u00e9e, B. Algorithms for computing signs of 2\u00d72 determinants: dynamics and average-case analysis. InAlgorithms\u2014ESA \u201997, G. W. R. Burkhard, ed., no. 1136 in Lecture Notes in Computer Science, pp. 486\u2013499. Springer-Verlag, Berlin, 1997. Proceedings of the Fifth European Symposium on Algorithms, Graz, September 1997."},{"issue":"2","key":"BF02679623_CR61","doi-asserted-by":"crossref","first-page":"101","DOI":"10.4064\/aa-81-2-101-144","volume":"81","author":"B. Vall\u00e9e","year":"1997","unstructured":"Vall\u00e9e, B. Op\u00e9rateurs de Ruelle-Mayer g\u00e9n\u00e9ralis\u00e9s et analyse des algorithmes d\u2019Euclide et de Gauss.Acta Arithmetica 81(2) (1997), 101\u2013144.","journal-title":"Acta Arithmetica"},{"issue":"4","key":"BF02679623_CR62","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1007\/PL00009246","volume":"22","author":"B. Vall\u00e9e","year":"1998","unstructured":"Vall\u00e9e, B. Dynamics of the binary euclidean algorithm: functional analysis and operators.Algorithmica 22(4) (1998), 660\u2013685.","journal-title":"Algorithmica"},{"key":"BF02679623_CR63","unstructured":"Vall\u00e9e, B. Dynamical sources in information theory: fundamental intervals and words prefixes.Algorithmica, this issue."},{"key":"BF02679623_CR64","unstructured":"Vall\u00e9e, B., and Lem\u00e9e, C. Average-case analyses of three algorithms for computing the jacobi symbol. Rapport de Recherche de l\u2019Universit\u00e9 de Caen, Les Cahiers du GREYC # 1, 1999."},{"key":"BF02679623_CR65","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/0020-0190(80)90008-3","volume":"11","author":"A. C.-C. Yao","year":"1980","unstructured":"Yao, A. C.-C. A note on the analysis of extendible hashing.Information Processing Letters 11 (1980), 84\u201386.","journal-title":"Information Processing Letters"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02679623.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02679623\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02679623","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T11:52:18Z","timestamp":1558353138000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02679623"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,2]]},"references-count":65,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,2]]}},"alternative-id":["BF02679623"],"URL":"https:\/\/doi.org\/10.1007\/bf02679623","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,2]]}}}