On substitution invariant sturmian words : an application of Rauzy fractals
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 3, pp. 329-349.

sturmian words are infinite words that have exactly n+1 factors of length n for every positive integer n. A sturmian word s α,ρ is also defined as a coding over a two-letter alphabet of the orbit of point ρ under the action of the irrational rotation R α :xx+α (mod 1). A substitution fixes a sturmian word if and only if it is invertible. The main object of the present paper is to investigate Rauzy fractals associated with two-letter invertible substitutions. As an application, we give an alternative geometric proof of Yasutomi’s characterization of all pairs (α,ρ) such that s α,ρ is a fixed point of some non-trivial substitution.

DOI : https://doi.org/10.1051/ita:2007026
Classification : 11J70,  37B10,  68R15
Mots clés : sturmian words, Rauzy fractals, invertible substitutions, automorphisms of the free monoid, tilings
@article{ITA_2007__41_3_329_0,
     author = {Berth\'e, Val\'erie and Ei, Hiromi and Ito, Shunji and Rao, Hui},
     title = {On substitution invariant sturmian words : an application of Rauzy fractals},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {329--349},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {3},
     year = {2007},
     doi = {10.1051/ita:2007026},
     zbl = {1140.11014},
     mrnumber = {2354361},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2007026/}
}
Berthé, Valérie; Ei, Hiromi; Ito, Shunji; Rao, Hui. On substitution invariant sturmian words : an application of Rauzy fractals. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 3, pp. 329-349. doi : 10.1051/ita:2007026. http://archive.numdam.org/articles/10.1051/ita:2007026/

[1] S. Akiyama, and N. Gjini, Connectedness of number theoretic tilings. Arch. Math. (Basel) 82 (2004) 153-163. | Zbl 1063.37008

[2] C. Allauzen, Une caractérisation simple des nombres de Sturm. J. Théor. Nombres Bordeaux 10 (1998) 237-241. | Numdam | Zbl 0930.11051

[3] P. Arnoux, and S. Ito, Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 181-207. | Zbl 1007.37001

[4] P. Baláži, S. Masáková, and E. Pelantová, Complete characterization of substitution invariant Sturmian sequences. Integers: electronic journal of combinatorial number theory 5 (2005) A14. | MR 2192233 | Zbl 1121.11020

[5] M. Barge, and B. Diamond, Coincidence for substitutions of Pisot type, Bull. Soc. Math. France 130 (2002) 619-626. | Numdam | Zbl 1028.37008

[6] D. Bernardi, A. Guerziz, and M. Koskas, Sturmian Words: description and orbits. Preprint.

[7] J. Berstel, and P. Séébold, A remark on morphic Sturmian words. RAIRO-Theor. Inf. Appl. 28 (1994) 255-263. | Numdam | Zbl 0883.68104

[8] J. Berstel, and P. Séébold, Morphismes de Sturm. Bull. Belg. Math. Soc. Simon Stevin 1 (1994) 175-189. | Zbl 0803.68095

[9] V. Berthé, and L. Vuillon, Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences. Discrete Math. 223 (2000) 27-53. | Zbl 0970.68124

[10] V. Berthé, C. Holton, and L.Q. Zamboni, Initial powers of Sturmian words. Acta Arith. 122 (2006) 315-347. | Zbl 1117.37005

[11] T.C. Brown, Descriptions of the characteristic sequence of an irrational. Canad. Math. Bull. 36 (1993) 15-21. | Zbl 0804.11021

[12] V. Canterini, Connectedness of geometric representation of substitutions of Pisot type. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 77-89. | Zbl 1031.37015

[13] E.M. Coven, and G.A. Hedlund, Sequences with minimal block growth. Math. Syst. Theory 7 (1973) 138-153. | Zbl 0256.54028

[14] D. Crisp, W. Moran, A. Pollington, and P. Shiue, Substitution invariant cutting sequence. J. Théor. Nombres Bordeaux 5 (1993) 123-137. | Numdam | Zbl 0786.11041

[15] H. Ei, and S. Ito, Decomposition theorem on invertible substitutions. Osaka J. Math. 35 (1998) 821-834. | Zbl 0924.20040

[16] I. Fagnot, A little more about morphic Sturmian words. RAIRO-Theor. Inf. Appl. 40 (2006), 511-518. | Numdam | Zbl 1110.68118

[17] K. Falconer, Techniques in Fractal Geometry. Oxford University Press, 5th edition (1979).

[18] S. Ito, and H. Rao, Purely periodic β-expansions with Pisot unit base. Proc. Amer. Math. Soc. 133 (2005) 953-964. | Zbl 1099.11062

[19] S. Ito, and H. Rao, Atomic surfaces, tilings and coincidence I. Irreducible case. Israel J. Math. 153 (2006) 129-156.

[20] S. Ito, and Y. Sano, On periodic β-expansions of Pisot numbers and Rauzy fractals. Osaka J. Math. 38 (2001) 349-368. | Zbl 0991.11040

[21] S. Ito, and S. Yasutomi, On continued fractions, substitutions and characteristic sequences [nx+y]-[(n-1)x+y]. Japan J. Math. 16 (1990) 287-306. | Zbl 0721.11009

[22] T. Komatsu, and A.J. Van Der Poorten, Substitution invariant Beatty sequences. Japan J. Math., New Ser. 22 (1996) 349-354. | Zbl 0868.11015

[23] M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002). | MR 1905123 | Zbl 1001.68093

[24] F. Mignosi, and P. Séébold, Morphismes sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux 5 (1993) 221-233. | Numdam | Zbl 0797.11029

[25] M. Morse, and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM 66.0188.03

[26] B. Parvaix, Propriétés d'invariance des mots sturmiens. J. Théor. Nombres Bordeaux 9 (1997) 351-369. | Numdam | Zbl 0904.11008

[27] B. Parvaix, Substitution invariant Sturmian bisequences. J. Théor. Nombres Bordeaux 11 (1999) 201-210. | Numdam | Zbl 0978.11005

[28] N. Pytheas Fogg, Substitutions in Arithmetics, Dynamics and Combinatorics, V. Berthé, S. Ferenczi, C.Mauduit, A. Siegel Eds., Springer Verlag. Lect. Notes Math. 1794 (2002). | MR 1970385 | Zbl 1014.11015

[29] M. Queffélec, Substitution Dynamical Systems. Spectral Analysis, Springer-Verlag. Lect. Notes Math. 1294 (1987). | MR 924156 | Zbl 0642.28013

[30] G. Rauzy, Nombres algebriques et substitutions, Bull. Soc. Math. France 110 (1982) 147-178. | Numdam | Zbl 0522.10032

[31] P. Séébold, On the conjugation of standard morphisms. Theoret. Comput. Sci. 195 (1998) 91-109. | Zbl 0981.68104

[32] V. Sirvent, and Y. Wang, Geometry of Rauzy fractals. Pacific J. Math. 206 (2002) 465-485. | Zbl 1048.37015

[33] B. Tan, and Z.-Y. Wen, Invertible substitutions and Sturmian sequences. European J. Combinatorics 24 (2003) 983-1002. | Zbl 1040.11014

[34] Z.-X. Wen, and Wen Z.-Y., Local isomorphisms of invertible substitutions. C. R. Acad. Sci. Paris Sér. I 318 (1994) 299-304. | Zbl 0812.11018

[35] S.-I. Yasutomi, On Sturmian sequences which are invariant under some substitutions, in Number theory and its applications (Kyoto, 1997). Kluwer Acad. Publ., Dordrecht (1999) 347-373. | Zbl 0971.11007