Prefix-suffix automaton associated with a primitive substitution. (Automate des préfixes-suffixes associé à une substitution primitive.) (French) Zbl 1071.37011

This paper deals with substitutive dynamical systems. It is proved that a dynamical system \(\Omega\) arising from a primitive substitution is measurably conjugate to an adic transformation (in the sense of A. M. Vershik) on a subshift of finite type. This subshift is defined as the set of paths on a graph called the prefix-suffix automaton and which has been introduced in a weaker form by G. Rauzy for instance in [Sequences defined by iterated morphisms. Sequences, combinatorics, compression, and transmission, Pap. Adv. Int. Workshop, Naples/Italy 1988, 275–286 (1990; Zbl 0955.28501)]. The authors prove that the conjugation map is one-to-one except on the orbit of periodic points of \(\Omega\), on which it is finite-to-one. They deduce a sequence of partitions of \(\Omega\) which is generating in measure. This work is completed by the other article of the authors [Trans. Am. Math. Soc. 353, No. 12, 5121–5144 (2001; Zbl 1142.37302)] where this approach allows them to obtain geometric representations for some of these systems as irrational translations on tori.


37B15 Dynamical aspects of cellular automata
11B85 Automata sequences
28A80 Fractals
28D05 Measure-preserving transformations
37B10 Symbolic dynamics
Full Text: DOI Numdam EuDML EMIS


[1] Canterini, V., Siegel, A., Geometric representation of primitive substitutions of Pisot type. À paraître dans Trans. Amer. Math. Soc. (2001). · Zbl 1142.37302
[2] Coven, E.M., Keane, M.S., The structure of substitution minimal sets. Trans. Amer. Math. Soc.162 (1971), 89-102. · Zbl 0205.28303
[3] Dekking, F.M., The spectrum of dynamical systems arising from substitutions of constant length. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete41 (1978), 221-239. · Zbl 0348.54034
[4] Dumont, J.-M., Thomas, A., Systèmes de numération et fonctions fractales relatifs aux substitutions. Theoret. Comput. Sci.65 (1989), 153-169. · Zbl 0679.10010
[5] Durand, F., Host, B., Skau, C., Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergodic Theory Dynam. Systems19 (1999), 953-993. · Zbl 1044.46543
[6] Grabner, P.J., Liardet, P., Tichy, R.F., Odometers and systems of numeration. Acta Arith.70 (1995), 103-123. · Zbl 0822.11008
[7] Herman, R.H., Putnam, I.F., Skau, C.F., Ordered Bratteli diagrams, dimension groups and topological dynamics. Internat. J. Math.3 (1992), 827-864. · Zbl 0786.46053
[8] Holton, C., Zamboni, L.Q., Geometric realizations of substitutions. Bull. Soc. Math. France126 (1998), 149-179. · Zbl 0931.11004
[9] Holton, C., Zamboni, L.Q., Directed graphs and substitutions. Preprint, 1999. · Zbl 0993.68075
[10] Kamae, T., Linear expansions, strictly ergodic homogeneous cocycles and fractals. Israel J. Math.106 (1998), 313-337. · Zbl 0914.28014
[11] Lind, D., Marcus, B., An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge, 1995. · Zbl 1106.37301
[12] Livshits, A.N., Sufficient conditions for weak mixing of substitutions and of stationary adic transformations. Mat. Zametki44 (1988), 785-793. English translation: Math. Notes44 (1988), 920-925. · Zbl 0713.28011
[13] Maes, A., Morphic predicates and applications to the decidability of arithmetic theories. Thèse de doctorat, Université de Mons-Hainault, 1999.
[14] Martin, J.C., Minimal flows arising from substitutions of non-constant length. Math. Systems Theory7 (1973), 73-82. · Zbl 0256.54026
[15] Mossé, B., Reconnaissabilité des substitutions et complexité des suites automatiques. Bull. Soc. Math. France124, (1996), 329-346. · Zbl 0855.68072
[16] Narbel, P., The boundary of iterated morphisms on free semi-groups. Internat. J. Algebra Comput.6 (1996), 229-260. · Zbl 0852.68074
[17] Queffélec, M., Substitution dynamical systems-spectral analysis. 1294, Springer-Verlag, Berlin, 1987. · Zbl 0642.28013
[18] Rauzy, G., Nombres algébriques et substitutions. Bull. Soc. Math. France110 (1982), 147-178. · Zbl 0522.10032
[19] Rauzy, G., Rotations sur les groupes, nombres algébriques, et substitutions. Dans Séminaire de Théorie des Nombres, 1987- 1988 (Talence, 1987-1988), Univ. Bordeaux I, Talence, 1988. Exp. No. 21. · Zbl 0726.11019
[20] Sirvent, V.F., Modelos geométricos asociados a substituciones. Trabajo de ascenso, Universidad Simón Bolivar, 1998.
[21] Vershik, A.M., Uniform algebraic approximation of shift and multiplication operators. Dokl. Akad. Nauk SSSR259 (1981), 526-529. English translation: Soviet Math. Dokl.24 (1981), 97-100. · Zbl 0484.47005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.