Abstract
A quite general model of source that comes from dynamical systems theory is introduced. Within this model, some basic problems of algorithmic information theory contexts are analysed. The main tool is a new object, the generalized Ruelle operator, which can be viewed as a “generating” operator for fundamental intervals (associated to information sharing common prefixes). Its dominant spectral objects are linked with important parameters of the source, such as the entropy, and play a central rôle in all the results.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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–C17. Full paper inAlgorithmica,17 (1997), 111–132.
Bedford, T., Keane, M., and Series, C., eds.Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces. Oxford University Press, 1991.
Beeler, M., Gosper, R. W., and Schroeppel, R. HAKMEM. Memorandum 239, Artificial Intelligence Laboratory, M.I.T., Feb. 1972.
Billingsley, P.Ergodic Theory and Information. Wiley, New York, 1965.
Bogomolny, E. B., and Carioli, M. Quantum maps from transfer operators.Physica D 67 (1993), 88–112.
Daudé, H., Flajolet, P., and Vallée, B. An average-case analysis of the Gaussian algorithm for lattice reduction.Combinatorics, Probability and Computing 6 (1997), 397–433.
Delange, H. Généralisation du Théorème d’Ikehara.Annales Scientifiques de l’Ecole Normale Supériore 71 (1954), 213–242.
Devroye, L. A probabilistic analysis of the height of tries and of the complexity of triesort.Acta Informatica,21 (1984), 229–237.
Efrat, I. Dynamics of the continued fraction map and the spectral theory ofSL(2,Z).Inventiones Mathematicae 114 (1993), 207–218.
Faivre, C. Distribution of Lévy’s constants for quadratic numbers.Acta Arithmetica 61(1) (1992), 13–34.
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–472.
Flajolet, P., Gourdon, X., and Dumas, P. Mellin transforms and asymptotics: harmonic sums.Theoretical Computer Science 144(1–2) (1995), 3–58.
Flajolet, P., and Vallée, B. Continued fraction algorithms, functional operators and structure constants.Theoretical Computer Science 194 (1998), 1–34.
Grothendieck, A. Produits tensoriels topologiques et espaces nucléaires.Memoirs of the American Mathematical Society 16 (1955).
Grothendieck, A. La théorie de Fredholm.Bulletin de la Société Mathématique de France 84 (1956), 319–384.
Hwang, H.-K. Théorèmes limites pour les structures combinatoires et les fonctions arithmétiques. Ph.D. thesis, École Polytechnique, Dec. 1994.
Kato, T.Perturbation Theory for Linear Operators. Springer-Verlag, New York, 1980.
Knuth, D.E.Computers and Typesetting, MF: the program, Volume D. Addison-Wesley, Reading, MA, 1986.
Krasnoselskii, M.Positive Solutions of Operator Equations. Noordhoff, Groningen, 1964.
Lorch, E. R.Spectral Theory. Oxford University Press, New York, 1962.
Mayer, D. H. On a ζ function related to the continued fraction transformation.Bulletin de la Société Mathématique de France 104 (1976), 195–203.
Mayer, D. H. Spectral properties of certain composition operators arising in statistical mechanics,Communications in Mathematical Physics 68 (1979), 1–8.
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–222.
Mayer, D. H. Private communication.
Mischyavichyus, G. A. Estimate of the remainder in the limit theorem for the denominators of continued fractions. Litovskiǐ Matematičeskiǐ Sbornik21(3), (1987), 63–74.
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–343. Corrections, op. cit.47(1) (1997), 191–192.
Philipp, W. Ein zentraler Grenzwertsatz mit Anwendungen auf die Zahlentheorie.Zeitschrift für Wahrscheinlichkeitstheorie 8 (1967), 195–203.
Pollicott, M. A complex Ruelle-Perron-Frobenius Theorem and two counterexamples.Ergodic Theory and Dynamical Systems 4 (1984), 135–146.
Ruelle, D.Thermodynamic Formalism. Addison-Wesley, Reading, MA, 1978.
Ruelle, D.Dynamical Zeta Functions for Piecewise Monotone Maps of the Interval. Volume 4 of CRM Monograph Series. American Mathematical Society, Providence, RI, 1994.
Schwartz, H. Composition operators inH p. Ph.D. Thesis, University of Toledo.
Shannon, C. A mathematical theory of communication.Bell Systems Technical Journal 27 (1948), 379–423, 623–656.
Shapiro, J.Composition Operators and Classical Function Theory. Universitext: Tracts in Mathematics. Springer-Verlag, New York, 1993.
Shapiro, J. Compact composition operators on spaces of boundary regular holomorphic functions.Proceedings of the AMS 100 (1997), 49–57.
Shapiro, J., and Taylor, P.D. Compact, nuclear, and Hilbert-Schmidt composition operators onH 2.Indiana University Mathematics Journal 23 (1973), 471–496.
Szpankowski, W., and Frieze, A. Greedy algorithms for the shortest common superstring that are asymptotically optimal. Preprint, 1998
Szpankowski, W., and Luczak, T. A suboptimal lossy date compression based on appoximate pattern matching.IEEE Transactions on Information Theory 43(5) (1997), 1439–1451.
Tenenbaum, G.Introduction à la théorie analytique des nombres, vol. 13. Institut Élie Cartan, Nancy, 1990.
Vallée, B. Opérateurs de Ruelle-Mayer généralisés et analyse des algorithmes d’Euclide et de Gauss.Acta Arithmetica 81(2) (1997), 101–144.
Vallée, B. Algorithms for computing signs of 2×2 determinants: dynamics and average-case algorithms,Proceedings of the 8th Annual European Symposium on Algorithms, ESA ’97, pp. 486–499. LNCS 1284. Springer-Verlag, Berlin, 1997.
Welsh, D.Codes and Cryptography. Oxford Science Publications, Clarendon Press, Oxford, 1989.
Author information
Authors and Affiliations
Additional information
Communicated by H. Prodinger and W. Szpankowski.
Online publication October 6, 2000.
Rights and permissions
About this article
Cite this article
Vallée, B. Dynamical sources in information theory: Fundamental intervals and word prefixes. Algorithmica 29, 262–306 (2001). https://doi.org/10.1007/BF02679622
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02679622