{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T22:50:33Z","timestamp":1775515833080,"version":"3.50.1"},"reference-count":41,"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\/bf02679622","type":"journal-article","created":{"date-parts":[[2007,7,29]],"date-time":"2007-07-29T00:42:49Z","timestamp":1185669769000},"page":"262-306","source":"Crossref","is-referenced-by-count":34,"title":["Dynamical sources in information theory: Fundamental intervals and word prefixes"],"prefix":"10.1007","volume":"29","author":[{"given":"B.","family":"Vall\u00e9e","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02679622_CR1","unstructured":"Avnaim, F., Boissonnat, J.-D., Devillers, O., Preparata, F., and Yvinec, M. Evaluation of a new method to compute signs of determinants. InProceedings of the Eleventh Annual ACM Symposium on Computational Geometry, 1995, pp. C16\u2013C17. Full paper inAlgorithmica,17 (1997), 111\u2013132."},{"key":"BF02679622_CR2","unstructured":"Bedford, T., Keane, M., and Series, C., eds.Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces. Oxford University Press, 1991."},{"key":"BF02679622_CR3","unstructured":"Beeler, M., Gosper, R. W., and Schroeppel, R. HAKMEM. Memorandum 239, Artificial Intelligence Laboratory, M.I.T., Feb. 1972."},{"key":"BF02679622_CR4","volume-title":"Ergodic Theory and Information","author":"P. Billingsley","year":"1965","unstructured":"Billingsley, P.Ergodic Theory and Information. Wiley, New York, 1965."},{"key":"BF02679622_CR5","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"},{"key":"BF02679622_CR6","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":"BF02679622_CR7","doi-asserted-by":"crossref","first-page":"213","DOI":"10.24033\/asens.1023","volume":"71","author":"H. Delange","year":"1954","unstructured":"Delange, H. G\u00e9n\u00e9ralisation du Th\u00e9or\u00e8me d\u2019Ikehara.Annales Scientifiques de l\u2019Ecole Normale Sup\u00e9riore 71 (1954), 213\u2013242.","journal-title":"Annales Scientifiques de l\u2019Ecole Normale Sup\u00e9riore"},{"key":"BF02679622_CR8","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"},{"key":"BF02679622_CR9","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"},{"issue":"1","key":"BF02679622_CR10","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":"BF02679622_CR11","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"},{"issue":"1\u20132","key":"BF02679622_CR12","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) (1995), 3\u201358.","journal-title":"Theoretical Computer Science"},{"key":"BF02679622_CR13","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":"BF02679622_CR14","doi-asserted-by":"crossref","unstructured":"Grothendieck, A. Produits tensoriels topologiques et espaces nucl\u00e9aires.Memoirs of the American Mathematical Society 16 (1955).","DOI":"10.1090\/memo\/0016"},{"key":"BF02679622_CR15","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":"BF02679622_CR16","unstructured":"Hwang, H.-K. Th\u00e9or\u00e8mes limites pour les structures combinatoires et les fonctions arithm\u00e9tiques. Ph.D. thesis, \u00c9cole Polytechnique, Dec. 1994."},{"key":"BF02679622_CR17","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":"BF02679622_CR18","volume-title":"Computers and Typesetting, MF: the program, Volume D","author":"D.E. Knuth","year":"1986","unstructured":"Knuth, D.E.Computers and Typesetting, MF: the program, Volume D. Addison-Wesley, Reading, MA, 1986."},{"key":"BF02679622_CR19","volume-title":"Positive Solutions of Operator Equations","author":"M. Krasnoselskii","year":"1964","unstructured":"Krasnoselskii, M.Positive Solutions of Operator Equations. Noordhoff, Groningen, 1964."},{"key":"BF02679622_CR20","volume-title":"Spectral Theory","author":"E. R. Lorch","year":"1962","unstructured":"Lorch, E. R.Spectral Theory. Oxford University Press, New York, 1962."},{"key":"BF02679622_CR21","doi-asserted-by":"crossref","first-page":"195","DOI":"10.24033\/bsmf.1825","volume":"104","author":"D. H. Mayer","year":"1976","unstructured":"Mayer, D. H. On a \u03b6 function related to the continued fraction transformation.Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France 104 (1976), 195\u2013203.","journal-title":"Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France"},{"key":"BF02679622_CR22","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":"BF02679622_CR23","first-page":"175","volume-title":"Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces","author":"D. H. Mayer","year":"1991","unstructured":"Mayer, D. H. Continued fractions and related transformations. InErgodic Theory, Symbolic Dynamics and Hyperbolic Spaces, T. Bedford, M. Keane, and C. Series, eds. Oxford University Press, Oxford, 1991, pp. 175\u2013222."},{"key":"BF02679622_CR24","unstructured":"Mayer, D. H. Private communication."},{"issue":"3","key":"BF02679622_CR25","first-page":"63","volume":"21","author":"G. A. Mischyavichyus","year":"1987","unstructured":"Mischyavichyus, G. A. Estimate of the remainder in the limit theorem for the denominators of continued fractions. Litovski\u01d0 Matemati\u010deski\u01d0 Sbornik21(3), (1987), 63\u201374.","journal-title":"Litovski\u01d0 Matemati\u010deski\u01d0 Sbornik"},{"issue":"2","key":"BF02679622_CR26","doi-asserted-by":"crossref","first-page":"309","DOI":"10.2969\/jmsj\/04620309","volume":"46","author":"T. Morita","year":"1994","unstructured":"Morita, T. Local limit theorem and distribution of periodic orbits of Lasota-Yorke transformations with infinite Markov partitions.Journal of the Mathematical Society of Japan 46(2) (1994), 309\u2013343. Corrections, op. cit.47(1) (1997), 191\u2013192.","journal-title":"Journal of the Mathematical Society of Japan"},{"key":"BF02679622_CR27","first-page":"195","volume":"8","author":"W. Philipp","year":"1967","unstructured":"Philipp, W. Ein zentraler Grenzwertsatz mit Anwendungen auf die Zahlentheorie.Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie 8 (1967), 195\u2013203.","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie"},{"key":"BF02679622_CR28","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":"BF02679622_CR29","volume-title":"Thermodynamic Formalism","author":"D. Ruelle","year":"1978","unstructured":"Ruelle, D.Thermodynamic Formalism. Addison-Wesley, Reading, MA, 1978."},{"key":"BF02679622_CR30","series-title":"CRM Monograph Series","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. Volume 4 of CRM Monograph Series. American Mathematical Society, Providence, RI, 1994."},{"key":"BF02679622_CR31","unstructured":"Schwartz, H. Composition operators inH p . Ph.D. Thesis, University of Toledo."},{"key":"BF02679622_CR32","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"C. Shannon","year":"1948","unstructured":"Shannon, C. A mathematical theory of communication.Bell Systems Technical Journal 27 (1948), 379\u2013423, 623\u2013656.","journal-title":"Bell Systems Technical Journal"},{"key":"BF02679622_CR33","volume-title":"Universitext: Tracts in Mathematics","author":"J. Shapiro","year":"1993","unstructured":"Shapiro, J.Composition Operators and Classical Function Theory. Universitext: Tracts in Mathematics. Springer-Verlag, New York, 1993."},{"key":"BF02679622_CR34","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":"BF02679622_CR35","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.D. Compact, nuclear, and Hilbert-Schmidt composition operators onH 2.Indiana University Mathematics Journal 23 (1973), 471\u2013496.","journal-title":"Indiana University Mathematics Journal"},{"key":"BF02679622_CR36","unstructured":"Szpankowski, W., and Frieze, A. Greedy algorithms for the shortest common superstring that are asymptotically optimal. Preprint, 1998"},{"issue":"5","key":"BF02679622_CR37","doi-asserted-by":"crossref","first-page":"1439","DOI":"10.1109\/18.623143","volume":"43","author":"W. Szpankowski","year":"1997","unstructured":"Szpankowski, W., and Luczak, T. A suboptimal lossy date compression based on appoximate pattern matching.IEEE Transactions on Information Theory 43(5) (1997), 1439\u20131451.","journal-title":"IEEE Transactions on Information Theory"},{"key":"BF02679622_CR38","volume-title":"Introduction \u00e0 la th\u00e9orie analytique des nombres, vol. 13","author":"G. Tenenbaum","year":"1990","unstructured":"Tenenbaum, G.Introduction \u00e0 la th\u00e9orie analytique des nombres, vol. 13. Institut \u00c9lie Cartan, Nancy, 1990."},{"issue":"2","key":"BF02679622_CR39","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"},{"key":"BF02679622_CR40","first-page":"486","volume-title":"Proceedings of the 8th Annual European Symposium on Algorithms, ESA \u201997","author":"B. Vall\u00e9e","year":"1997","unstructured":"Vall\u00e9e, B. Algorithms for computing signs of 2\u00d72 determinants: dynamics and average-case algorithms,Proceedings of the 8th Annual European Symposium on Algorithms, ESA \u201997, pp. 486\u2013499. LNCS 1284. Springer-Verlag, Berlin, 1997."},{"key":"BF02679622_CR41","volume-title":"Codes and Cryptography","author":"D. Welsh","year":"1989","unstructured":"Welsh, D.Codes and Cryptography. Oxford Science Publications, Clarendon Press, Oxford, 1989."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02679622.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02679622\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02679622","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T07:52:18Z","timestamp":1558338738000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02679622"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,2]]},"references-count":41,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,2]]}},"alternative-id":["BF02679622"],"URL":"https:\/\/doi.org\/10.1007\/bf02679622","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,2]]}}}