On substitution invariant Sturmian words: an application of Rauzy fractals

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

RAIRO - Theoretical Informatics and Applications (2007)

  • Volume: 41, Issue: 3, page 329-349
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Berthé, Valérie, et al. "On substitution invariant Sturmian words: an application of Rauzy fractals." RAIRO - Theoretical Informatics and Applications 41.3 (2007): 329-349. <http://eudml.org/doc/250017>.

@article{Berthé2007,
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. },
author = {Berthé, Valérie, Ei, Hiromi, Ito, Shunji, Rao, Hui},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Sturmian words; Rauzy fractals; invertible substitutions; automorphisms of the free monoid; tilings},
language = {eng},
month = {9},
number = {3},
pages = {329-349},
publisher = {EDP Sciences},
title = {On substitution invariant Sturmian words: an application of Rauzy fractals},
url = {http://eudml.org/doc/250017},
volume = {41},
year = {2007},
}

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
DA - 2007/9//
PB - EDP Sciences
VL - 41
IS - 3
SP - 329
EP - 349
AB - 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.
LA - eng
KW - Sturmian words; Rauzy fractals; invertible substitutions; automorphisms of the free monoid; tilings
UR - http://eudml.org/doc/250017
ER -

References

top
  1. S. Akiyama, and N. Gjini, Connectedness of number theoretic tilings. Arch. Math. (Basel)82 (2004) 153–163.  
  2. C. Allauzen, Une caractérisation simple des nombres de Sturm. J. Théor. Nombres Bordeaux10 (1998) 237–241.  
  3. P. Arnoux, and S. Ito, Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin8 (2001) 181–207.  
  4. P. Baláži, S. Masáková, and E. Pelantová, Complete characterization of substitution invariant Sturmian sequences. Integers: electronic journal of combinatorial number theory5 (2005) A14.  
  5. M. Barge, and B. Diamond, Coincidence for substitutions of Pisot type, Bull. Soc. Math. France130 (2002) 619–626.  
  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.  
  8. J. Berstel, and P. Séébold, Morphismes de Sturm. Bull. Belg. Math. Soc. Simon Stevin1 (1994) 175–189.  
  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.  
  10. V. Berthé, C. Holton, and L.Q. Zamboni, Initial powers of Sturmian words. Acta Arith.122 (2006) 315–347.  
  11. T.C. Brown, Descriptions of the characteristic sequence of an irrational. Canad. Math. Bull.36 (1993) 15–21.  
  12. V. Canterini, Connectedness of geometric representation of substitutions of Pisot type. Bull. Belg. Math. Soc. Simon Stevin10 (2003) 77–89.  
  13. E.M. Coven, and G.A. Hedlund, Sequences with minimal block growth. Math. Syst. Theory7 (1973) 138–153.  
  14. D. Crisp, W. Moran, A. Pollington, and P. Shiue, Substitution invariant cutting sequence. J. Théor. Nombres Bordeaux5 (1993) 123–137.  
  15. H. Ei, and S. Ito, Decomposition theorem on invertible substitutions. Osaka J. Math.35 (1998) 821–834.  
  16. I. Fagnot, A little more about morphic Sturmian words. RAIRO-Theor. Inf. Appl.40 (2006), 511–518.  
  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.  
  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.  
  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.  
  22. T. Komatsu, and A.J. van der Poorten, Substitution invariant Beatty sequences. Japan J. Math., New Ser.22 (1996) 349–354.  
  23. M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002).  
  24. F. Mignosi, and P. Séébold, Morphismes sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux5 (1993) 221–233.  
  25. M. Morse, and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math.62 (1940) 1–42.  
  26. B. Parvaix, Propriétés d'invariance des mots sturmiens. J. Théor. Nombres Bordeaux9 (1997) 351–369.  
  27. B. Parvaix, Substitution invariant Sturmian bisequences. J. Théor. Nombres Bordeaux11 (1999) 201–210.  
  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).  
  29. M. Queffélec, Substitution Dynamical Systems. Spectral Analysis, Springer-Verlag. Lect. Notes Math.1294 (1987).  
  30. G. Rauzy, Nombres algebriques et substitutions, Bull. Soc. Math. France110 (1982) 147–178.  
  31. P. Séébold, On the conjugation of standard morphisms. Theoret. Comput. Sci.195 (1998) 91–109.  
  32. V. Sirvent, and Y. Wang, Geometry of Rauzy fractals. Pacific J. Math.206 (2002) 465–485.  
  33. B. Tan, and Z.-Y. Wen, Invertible substitutions and Sturmian sequences. European J. Combinatorics24 (2003) 983–1002.  
  34. Z.-X. Wen, and Wen Z.-Y., Local isomorphisms of invertible substitutions. C. R. Acad. Sci. Paris Sér. I318 (1994) 299–304.  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.