On substitution invariant sturmian words : an application of Rauzy fractals

Berthé, Valérie; Ei, Hiromi; Ito, Shunji; Rao, Hui

Berthé, Valérie ; Ei, Hiromi ; Ito, Shunji ; Rao, Hui

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007), p. 329-349 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

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_{α} : x \mapsto x + α$ (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.

Publié le : 2007-01-01

MR 2354361 | Zbl 1140.11014 | 2 citations dans Numdam

DOI : https://doi.org/10.1051/ita:2007026
Classification: 11J70, 37B10, 68R15

@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},
     volume = {41},
     year = {2007},
     pages = {329-349},
     doi = {10.1051/ita:2007026},
     mrnumber = {2354361},
     zbl = {1140.11014},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2007__41_3_329_0}
}

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) pp. 329-349. doi : 10.1051/ita:2007026. http://gdmltest.u-ga.fr/item/ITA_2007__41_3_329_0/

Bibliographie

[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. | Zbl pre05256319

[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 $[n x + 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