Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-30T18:55:03.985Z Has data issue: false hasContentIssue false
  • English
  • Français

On substitution invariant Sturmian words: an application of Rauzy fractals

Published online by Cambridge University Press:  25 September 2007

Valérie Berthé ,
Hiromi Ei ,
Shunji Ito  and
Hui Rao
Valérie Berthé
Affiliation:
LIRMM 161 rue Ada F-34392 Montpellier cedex 5, France; [email protected]
Hiromi Ei
Affiliation:
Department of Information and System Engineering, Faculty of Science Engineering, 1-13-27 Kasuga, Bunkyo-ku, Tokyo 112-8851, Japan
Shunji Ito
Affiliation:
Department of Information and System Engineering, Kanazawa University, Kanazawa, Japan
Hui Rao
Affiliation:
Department of Mathematics, Tsinghua University, Beijing, China
Get access

Abstract

Sturmian words are infinite words that have exactly n+1 factors of length n for every positive integer n. A Sturmian word sα,p 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 → 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 (α,p) such that sα,p is a fixed point of some non-trivial substitution.

Keywords

Sturmian wordsRauzy fractalsinvertible substitutionsautomorphisms of the free monoidtilings
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 41 , Issue 3 , July 2007 , pp. 329 - 349
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Akiyama, S., and Gjini, N., Connectedness of number theoretic tilings. Arch. Math. (Basel) 82 (2004) 153–163. CrossRef
Allauzen, C., Une caractérisation simple des nombres de Sturm. J. Théor. Nombres Bordeaux 10 (1998) 237–241. CrossRef
Arnoux, P., and Ito, S., Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 181–207.
Balá, P.ži, S. Masáková, and E. Pelantová, Complete characterization of substitution invariant Sturmian sequences. Integers: electronic journal of combinatorial number theory 5 (2005) A14.
M. Barge, and B. Diamond, Coincidence for substitutions of Pisot type, Bull. Soc. Math. France 130 (2002) 619–626. CrossRef
D. Bernardi, A. Guerziz, and M. Koskas, Sturmian Words: description and orbits. Preprint.
Berstel, J., and Séébold, P., A remark on morphic Sturmian words. RAIRO-Theor. Inf. Appl. 28 (1994) 255–263. CrossRef
Berstel, J., and Séébold, P., Morphismes de Sturm. Bull. Belg. Math. Soc. Simon Stevin 1 (1994) 175–189.
Berthé, V., and Vuillon, L., Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences. Discrete Math. 223 (2000) 27–53. CrossRef
Berthé, V., Holton, C., and Zamboni, L.Q., Initial powers of Sturmian words. Acta Arith. 122 (2006) 315–347. CrossRef
Brown, T.C., Descriptions of the characteristic sequence of an irrational. Canad. Math. Bull. 36 (1993) 15–21. CrossRef
Canterini, V., Connectedness of geometric representation of substitutions of Pisot type. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 77–89.
Coven, E.M., and Hedlund, G.A., Sequences with minimal block growth. Math. Syst. Theory 7 (1973) 138–153. CrossRef
Crisp, D., Moran, W., Pollington, A., and Shiue, P., Substitution invariant cutting sequence. J. Théor. Nombres Bordeaux 5 (1993) 123–137. CrossRef
Ei, H., and Ito, S., Decomposition theorem on invertible substitutions. Osaka J. Math. 35 (1998) 821–834.
I. Fagnot, A little more about morphic Sturmian words. RAIRO-Theor. Inf. Appl. 40 (2006), 511–518.
K. Falconer, Techniques in Fractal Geometry. Oxford University Press, 5th edition (1979).
Ito, S., and Rao, H., Purely periodic β-expansions with Pisot unit base. Proc. Amer. Math. Soc. 133 (2005) 953–964. CrossRef
Ito, S., and Rao, H., Atomic surfaces, tilings and coincidence I. Irreducible case. Israel J. Math. 153 (2006) 129–156. CrossRef
Ito, S., and Sano, Y., On periodic β-expansions of Pisot numbers and Rauzy fractals. Osaka J. Math. 38 (2001) 349–368.
Ito, S., and Yasutomi, S., On continued fractions, substitutions and characteristic sequences [nx + y] - [(n - 1)x + y]. Japan J. Math. 16 (1990) 287–306.
T. Komatsu, and A.J. van der Poorten, Substitution invariant Beatty sequences. Japan J. Math., New Ser. 22 (1996) 349–354.
M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002).
Mignosi, F., and Séébold, P., Morphismes sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux 5 (1993) 221–233. CrossRef
Morse, M., and Hedlund, G.A., Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1–42. CrossRef
Parvaix, B., Propriétés d'invariance des mots sturmiens. J. Théor. Nombres Bordeaux 9 (1997) 351–369. CrossRef
Parvaix, B., Substitution invariant Sturmian bisequences. J. Théor. Nombres Bordeaux 11 (1999) 201–210. CrossRef
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).
M. Queffélec, Substitution Dynamical Systems. Spectral Analysis, Springer-Verlag. Lect. Notes Math. 1294 (1987).
G. Rauzy, Nombres algebriques et substitutions, Bull. Soc. Math. France 110 (1982) 147–178. CrossRef
Séébold, P., On the conjugation of standard morphisms. Theoret. Comput. Sci. 195 (1998) 91–109. CrossRef
Sirvent, V., and Wang, Y., Geometry of Rauzy fractals. Pacific J. Math. 206 (2002) 465–485. CrossRef
Tan, B., and Wen, Z.-Y., Invertible substitutions and Sturmian sequences. European J. Combinatorics 24 (2003) 983–1002. CrossRef
Wen, Z.-X., and Wen Z.-Y., Local isomorphisms of invertible substitutions. C. R. Acad. Sci. Paris Sér. I 318 (1994) 299–304.
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.