Coding of substitution dynamical systems as shifts of finite type

About the paper

language English
published in Ergodic Theory and Dynamical Systems 38, No. 3 (2016)
pages 944 to 973
DOI 10.1017/etds.2014.80
supported by FAPESP, process 2009/07744-0

Abstract

We develop a theory that allows us to code dynamical systems induced by primitive substitutions continuously as shift of finite type in many different ways. The well-known prefix-suffix coding turns out to correspond to one special case. We precisely analyse the basic properties of these codings (injectivity, coding of the periodic points, properties of the presentation graph, interaction with the shift map). A lot of examples illustrate the theory and show that, depending on the particular coding, several amazing effects may occur. The results give new insights in the theory of substitution dynamical systems and might serve as a powerful tool for further researches.

References

  1. V. Berthé, A. Siegel, Tilings associated with beta-numeration and substitutions, Integers 5 (2005) (electronic).
  2. V. Canterini, A. Siegel, Automate des préfixes-suffixes associé à une substitution primitive, J. Théor. Nombres Bordeaux 13 (2001) 353—369.
  3. V. Canterini, A. Siegel, Geometric representation of substitutions of Pisot type, Trans. Amer. Math. Soc. 353 (2001) 5121—5144 (electronic).
  4. F. Durand, B. Host, and C. Skau, Substitutional dynamical systems, Bratteli diagrams and dimension groups, Ergodic Theory Dynam. Systems 19 (1999), pp. 953—993.
  5. N. P. Fogg, Substitutions in dynamics, arithmetics and combinatorics, vol. 1794 of Lecture Notes in Mathematics, Springer-Verlag, Berlin, 2002. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel.
  6. A. H. Forrest, K-groups associated with substitution minimal systems, Israel J. Math. 98 (1997), pp. 101—139.
  7. T. Harju and M. Linna, On the periodicity of morphisms on free monoids, RAIRO, Inf. Th´eor. Appl. 20 (1986), pp. 47—54.
  8. C. Holton and L. Q. Zamboni, Directed graphs and substitutions, Theory Comput. Syst. 34 (2001), pp. 545—564.
  9. D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995.
  10. B. Mossé, Puissances de mots et reconnaissabilité des points fixes d´une substitution, Theoret. Comput. Sci. 99 (1992), pp. 327—334.
  11. B. Mossé, Recognizability of substitutions and complexity of automatic sequences, Bull. Soc. Math. Fr. 124 (1996), pp. 329—346.
  12. J.-J. Pansiot, Decidability of periodicity for infinite words, RAIRO, Inf. Théor. Appl. 20 (1986), pp. 43—46.
  13. M. Queffélec, Substitution dynamical systems. Spectral analysis. 2nd ed., Lecture Notes in Mathematics 1294. Dordrecht: Springer. xv, 351 p., 2010.
  14. A. M. Vershik, Uniform algebraic approximation of shift and multiplication operators, Dokl. Akad. Nauk SSSR 259 (1981), pp. 526—529.
  15. A. M. Vershik and A. N. Livshits, Adic models of ergodic transformations, spectral theory, substitutions, and related topics, in Representation theory and dynamical systems, vol. 9 of Adv. Soviet Math., Amer. Math. Soc., Providence, RI, 1992, pp. 185—204.

Links

Ergodic Theory and Dynamical Systems
Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)