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 : 10.1051/ita:2007026
Classification : 11J70, 37B10, 68R15
Mots clés : sturmian words, Rauzy fractals, invertible substitutions, automorphisms of the free monoid, tilings
Berthé, Valérie  ; Ei, Hiromi 1 ; Ito, Shunji 2 ; Rao, Hui 3

1 Chuo University Kasuga, Bunkyo-ku Department of Information and System Engineering Tokyo (Japan)
2 Kanazawa University Department of Mathematical Kanazawa (Japan)
3 Tsinghua University Department of Mathematics Beijing (China)
@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},
     mrnumber = {2354361},
     zbl = {1140.11014},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2007026/}
}
TY  - JOUR
AU  - Berthé, Valérie
AU  - Ei, Hiromi
AU  - Ito, Shunji
AU  - Rao, Hui
TI  - On substitution invariant sturmian words : an application of Rauzy fractals
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2007
SP  - 329
EP  - 349
VL  - 41
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007026/
DO  - 10.1051/ita:2007026
LA  - en
ID  - ITA_2007__41_3_329_0
ER  - 
%0 Journal Article
%A Berthé, Valérie
%A Ei, Hiromi
%A Ito, Shunji
%A Rao, Hui
%T On substitution invariant sturmian words : an application of Rauzy fractals
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2007
%P 329-349
%V 41
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2007026/
%R 10.1051/ita:2007026
%G en
%F 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) no. 3, pp. 329-349. doi : 10.1051/ita:2007026. http://www.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

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

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

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

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

[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

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

[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

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

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

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

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

[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

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

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

[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

[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

[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

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

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

[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

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

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

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

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

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

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

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

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

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

[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

[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

Cité par Sources :