Episturmian words: a survey

Amy Glen; Jacques Justin

RAIRO - Theoretical Informatics and Applications (2009)

  • Volume: 43, Issue: 3, page 403-442
  • ISSN: 0988-3754

Abstract

top
In this paper, we survey the rich theory of infinite episturmian words which generalize to any finite alphabet, in a rather resembling way, the well-known family of Sturmian words on two letters. After recalling definitions and basic properties, we consider episturmian morphisms that allow for a deeper study of these words. Some properties of factors are described, including factor complexity, palindromes, fractional powers, frequencies, and return words. We also consider lexicographical properties of episturmian words, as well as their connection to the balance property, and related notions such as finite episturmian words, Arnoux-Rauzy sequences, and “episkew words” that generalize the skew words of Morse and Hedlund.

How to cite

top

Glen, Amy, and Justin, Jacques. "Episturmian words: a survey." RAIRO - Theoretical Informatics and Applications 43.3 (2009): 403-442. <http://eudml.org/doc/250585>.

@article{Glen2009,
abstract = { In this paper, we survey the rich theory of infinite episturmian words which generalize to any finite alphabet, in a rather resembling way, the well-known family of Sturmian words on two letters. After recalling definitions and basic properties, we consider episturmian morphisms that allow for a deeper study of these words. Some properties of factors are described, including factor complexity, palindromes, fractional powers, frequencies, and return words. We also consider lexicographical properties of episturmian words, as well as their connection to the balance property, and related notions such as finite episturmian words, Arnoux-Rauzy sequences, and “episkew words” that generalize the skew words of Morse and Hedlund. },
author = {Glen, Amy, Justin, Jacques},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Combinatorics on words; episturmian words; Arnoux-Rauzy sequences; Sturmian words; episturmian morphisms.; combinatorics on words; episturmian morphisms},
language = {eng},
month = {3},
number = {3},
pages = {403-442},
publisher = {EDP Sciences},
title = {Episturmian words: a survey},
url = {http://eudml.org/doc/250585},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Glen, Amy
AU - Justin, Jacques
TI - Episturmian words: a survey
JO - RAIRO - Theoretical Informatics and Applications
DA - 2009/3//
PB - EDP Sciences
VL - 43
IS - 3
SP - 403
EP - 442
AB - In this paper, we survey the rich theory of infinite episturmian words which generalize to any finite alphabet, in a rather resembling way, the well-known family of Sturmian words on two letters. After recalling definitions and basic properties, we consider episturmian morphisms that allow for a deeper study of these words. Some properties of factors are described, including factor complexity, palindromes, fractional powers, frequencies, and return words. We also consider lexicographical properties of episturmian words, as well as their connection to the balance property, and related notions such as finite episturmian words, Arnoux-Rauzy sequences, and “episkew words” that generalize the skew words of Morse and Hedlund.
LA - eng
KW - Combinatorics on words; episturmian words; Arnoux-Rauzy sequences; Sturmian words; episturmian morphisms.; combinatorics on words; episturmian morphisms
UR - http://eudml.org/doc/250585
ER -

References

top
  1. B. Adamczewski, Balances for fixed points of primitive substitutions. Theoret. Comput. Sci.307 (2003) 47–75.  
  2. B. Adamczewski and Y. Bugeaud, Palindromic continued fractions. Ann. Inst. Fourier (Grenoble)57 (2007) 1557–1574.  
  3. B. Adamczewski and Y. Bugeaud, Transcendence measure for continued fractions involving repetitive or symmetric patterns. J. Eur. Math. Soc., to appear.  
  4. P. Alessandri and V. Berthé, Three distance theorems and combinatorics on words. Enseign. Math.44 (1998) 103–132.  
  5. J.-P. Allouche and A. Glen, Extremal properties of (epi)sturmian sequences and distribution modulo 1, in preparation.  
  6. J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, UK (2003).  
  7. J.-P. Allouche, J.L. Davison, M. Queffélec and L.Q. Zamboni, Transcendence of Sturmian or morphic continued fractions. J. Number Theory91 (2001) 39–66.  
  8. P. Ambrož, C. Frougny, Z. Masáková and E. Pelantová, Palindromic complexity of infinite words associated with simple Parry numbers. Ann. Inst. Fourier (Grenoble)56 (2006) 2131–2160.  
  9. A. Apostolico and M. Crochemore, String pattern matching for a deluge survival kit, in: Handbook of Massive Data Sets, Massive Comput., Vol. 4. Kluwer Acad. Publ., Dordrecht (2002).  
  10. A. Apostolico and A. Ehrenfeucht, Efficient detection of quasiperiodicities in strings. Theoret. Comput. Sci.119 (1993) 247–265.  
  11. P. Arnoux and S. Ito, Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin8 (2001) 181–207.  
  12. P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France119 (1991) 199–215.  
  13. Yu. Baryshnikov, Complexity of trajectories in rectangular billiards. Commun. Math. Phys.174 (1995) 43–56.  
  14. J. Berstel, On the index of Sturmian words, in: Jewels Are Forever. Springer-Verlag, Berlin (1999), pp. 287–294.  
  15. J. Berstel, Recent results on extensions of Sturmian words. Int. J. Algebra Comput.12 (2002) 371–385.  
  16. J. Berstel and P. Séébold, A characterization of Sturmian morphisms, in Mathematical Foundations of Computer Science 1993, edited by A.M. Borzyszkowski and S. Sokolowski. Springer-Verlag, Berlin, Lect. Notes Comput. Sci.711 (1993) 281–290.  
  17. J. Berstel and P. Séébold, A remark on morphic Sturmian words. Theor. Inform. Appl.28 (1994) 255–263.  
  18. J. Berstel and L. Vuillon, Coding rotations on intervals. Theoret. Comput. Sci.281 (2002) 99–107.  
  19. V. Berthé, Fréquences des facteurs des suites sturmiennes. Theoret. Comput. Sci.165 (1996) 295–309.  
  20. V. Berthé, Autour du système de numération d'Ostrowski. Bull. Belg. Math. Soc. Simon Stevin8 (2001) 209–239.  
  21. V. Berthé, S. Ferenczi and L.Q. Zamboni, Interactions between dynamics, arithmetics and combinatorics: the good, the bad, and the ugly, in: Algebraic and topological dynamics. Amer. Math. Soc., Providence, RI, Contemp. Math.385 (2005) 333–364.  
  22. V. Berthé, C. Holton and L.Q. Zamboni, Initial powers of Sturmian sequences. Acta Arith.122 (2006) 315–347.  
  23. V. Berthé, H. Ei, S. Ito and H. Rao, On substitution invariant Sturmian words: an application of Rauzy fractals. Theoret. Inform. Appl. 41 (2007) 329–349.  
  24. J.-P. Borel and F. Laubie, Quelques mots sur la droite projective réelle. J. Théor. Nombres Bordeaux 5 (1993) 23–51.  
  25. J.-P. Borel and C. Reutenauer, Palindromic factors of billiard words. Theoret. Comput. Sci.340 (2005) 334–348.  
  26. S. Brlek, S. Hamel, M. Nivat and C. Reutenauer, On the palindromic complexity of infinite words. Internat. J. Found. Comput. Sci.15 (2004) 293–306.  
  27. M. Bucci, A. de Luca, A. De Luca and L.Q. Zamboni, On some problems related to palindrome closure. RAIRO-Theor. Inf. Appl.42 (2008) 679-700.  
  28. M. Bucci, A. de Luca, A. De Luca and L.Q. Zamboni, On different generalizations of episturmian words. Theoret. Comput. Sci.393 (2008) 23–36.  
  29. M. Bucci, A. De Luca, A. Glen and L.Q. Zamboni, A connection between palindromic and factor complexity using return words, Adv. in Appl. Math.42 (2009) 60–74.  
  30. M. Bucci, A. De Luca, A. Glen and L.Q. Zamboni, A new characteristic property of rich words. Theoret. Comput. Sci. (in press), doi:.  DOI10.1016/j.tcs.2008.11.001
  31. J. Cassaigne, Sequences with grouped factors, in Developments in Language Theory III. Aristotle University of Thessaloniki, 1998, pp. 211–222.  
  32. J. Cassaigne and N. Chekhova, Fonctions de récurrence des suites d'Arnoux-Rauzy et réponse à une question de Morse et Hedlund. Ann. Inst. Fourier (Grenoble)56 (2006) 2249–2270.  
  33. J. Cassaigne, S. Ferenczi and L.Q. Zamboni, Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier (Grenoble)50 (2000) 1265–1276.  
  34. M.G. Castelli, F. Mignosi and A. Restivo, Fine and Wilf's theorem for three periods and a generalization of Sturmian words. Theoret. Comput. Sci.218 (1999) 83–94.  
  35. N. Chekhova, P. Hubert and A. Messaoudi, Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci. J. Théor. Nombres Bordeaux 13 (2001) 371–394.  
  36. E.M. Coven, Sequences with minimal block growth II. Math. Syst. Theor.8 (1974) 376–382.  
  37. E.M. Coven and G.A. Hedlund, Sequences with minimal block growth. Math. Syst. Theor.7 (1973) 138–153.  
  38. D. Crisp, W. Moran, A. Pollington and P. Shiue, Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux5 (1993) 123–137.  
  39. D. Damanik and D. Lenz, The index of Sturmian sequences. Eur. J. Combin.23 (2002) 23–29.  
  40. D. Damanik and L.Q. Zamboni, Combinatorial properties of Arnoux-Rauzy subshifts and applications to Schrödinger operators. Rev. Math. Phys.15 (2003) 745–763.  
  41. A. de Luca, Sturmian words: structure. combinatorics and their arithmetics. Theoret. Comput. Sci.183 (1997) 45–82.  
  42. A. de Luca, A. Glen and L.Q. Zamboni, Rich, Sturmian, and trapezoidal words. Theoret. Comput. Sci.407 (2008) 569–573.  
  43. X. Droubay and G. Pirillo, Palindromes and Sturmian words. Theoret. Comput. Sci.223 (1999) 73–85.  
  44. X. Droubay, J. Justin and G. Pirillo, Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci.255 (2001) 539–553.  
  45. F. Durand, A characterization of substitutive sequences using return words. Discrete Math.179 (1998) 89–101.  
  46. F. Durand, A generalization of Cobham's theorem. Theor. Comput. Syst.31 (1998) 169–185.  
  47. F. Durand, Linearly recurrent subshifts have a finite number of non-periodic subshift factors. Ergod. Theor. Dyn. Syst.19 (1999) 953–993.  
  48. I. Fagnot, A little more about morphic Sturmian words. RAIRO-Theor. Inf. Appl.40 (2006) 511–518.  
  49. I. Fagnot and L. Vuillon, Generalized balances in Sturmian words. Discrete Appl. Math.121 (2002) 83–101.  
  50. S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145–154.  
  51. S. Ferenczi and C. Mauduit, Transcendence of numbers with a low complexity expansion. J. Number Theory67 (1997) 146–161.  
  52. S. Ferenczi, C. Mauduit and A. Nogueira, Substitutional dynamical systems: algebraic characterization of eigenvalues. Ann. Sci. École Norm. Sup.29 (1995) 519–533.  
  53. S. Ferenczi, C. Holton and L.Q. Zamboni, Structure of three interval exchange transformations I. An arithmetic study. Ann. Inst. Fourier (Grenoble)51 (2001) 861–901.  
  54. S. Fischler, Palindromic prefixes and episturmian words. J. Comb. Th. (A)113 (2006) 1281–1304.  
  55. S. Fischler, Palindromic prefixes and diophantine approximation. Monatsh. Math.151 (2007) 11–37.  
  56. A.S. Fraenkel, Complementing and exactly covering sequences. J. Comb. Th. (A)14 (1973) 8–20.  
  57. A. Glen, On Sturmian and episturmian words, and related topics, Ph.D. Thesis. The University of Adelaide, Australia, April (2006).  
  58. A. Glen, Order and quasiperiodicity in episturmian words, in: Proceedings of the 6th International Conference on Words, Marseille, France, September 17–21, (2007) 144–158.  
  59. A. Glen, Powers in a class of 𝒜 -strict standard episturmian words. Theoret. Comput. Sci.380 (2007) 330–354.  
  60. A. Glen, A characterization of fine words over a finite alphabet. Theoret. Comput. Sci.391 (2008) 51–60.  
  61. A. Glen, J. Justin and G. Pirillo, Characterizations of finite and infinite episturmian words via lexicographic orderings. Eur. J. Combin.29 (2008) 45–58.  
  62. A. Glen, F. Levé and G. Richomme, Quasiperiodic and Lyndon episturmian words. Theoret. Comput. Sci.409 (2008) 578–600.  
  63. A. Glen, J. Justin, S. Widmer and L.Q. Zamboni, Palindromic richness. Eur. J. Combin.30 (2009) 510–531.  
  64. A. Glen, F. Levé and G. Richomme, Directive words of episturmian words: equivalences and normalization. RAIRO-Theor. Inf. Appl.43 (2009) 299–319.  
  65. E. Godelle, Représentation par des transvections des groupes dartin-tits. Group, Geometry and Dynamics1 (2007) 111–133.  
  66. A. Heinis and R. Tijdeman, Characterisation of asymptotically Sturmian sequences. Publ. Math. Debrecen56 (2000) 415–430.  
  67. C. Holton and L.Q. Zamboni, Descendants of primitive substitutions. Theor. Comput. Syst.32 (1999) 133–157.  
  68. P. Hubert, Suites équilibrés. Theoret. Comput. Sci.242 (2000) 91–108.  
  69. O. Jenkinson and L.Q. Zamboni, Characterisations of balanced words via orderings. Theoret. Comput. Sci310 (2004) 247–271.  
  70. J. Justin, On a paper by Castelli, Mignosi, Restivo. RAIRO-Theor. Inf. Appl.34 (2000) 373–377.  
  71. J. Justin, Episturmian morphisms and a Galois theorem on continued fractions. RAIRO-Theor. Inf. Appl.39 (2005) 207–215.  
  72. J. Justin and G. Pirillo, Fractional powers in Sturmian words. Theoret. Comput. Sci.255 (2001) 363–376.  
  73. J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Theoret. Comput. Sci.276 (2002) 281–313.  
  74. J. Justin and G. Pirillo, On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl.36 (2002) 385–388.  
  75. J. Justin and G. Pirillo, Episturmian words: shifts, morphisms and numeration systems. Internat. J. Found. Comput. Sci.15 (2004) 329–348.  
  76. J. Justin and L. Vuillon, Return words in Sturmian and episturmian words. RAIRO-Theor. Inf. Appl.34 (2000) 343–356.  
  77. T. Komatsu and A.J. van der Poorten, Substitution invariant Beatty sequences. Jpn J. Math.22 (1996) 349–354.  
  78. D. Krieger, On stabilizers of infinite words. Theoret. Comput. Sci.400 (2008) 169–181.  
  79. F. Levé and G. Richomme, Quasiperiodic infinite words: some answers. Bull. Eur. Assoc. Theor. Comput. Sci.84 (2004) 128–138.  
  80. F. Levé and G. Richomme, Quasiperiodic episturmian words, in: Proceedings of the 6th International Conference on Words. Marseille, France, September 17–21, 2007, pp. 201–211.  
  81. F. Levé and G. Richomme, Quasiperiodic Sturmian words and morphisms. Theoret. Comput. Sci.372 (2007) 15–25.  
  82. M. Lothaire, Combinatorics on Words, Vol. 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, Massachusetts (1983).  
  83. M. Lothaire, Algebraic Combinatorics on Words, Vol. 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, UK, (2002).  
  84. M. Lothaire, Applied Combinatorics on Words, Vol. 105 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, UK, (2005).  
  85. S. Marcus, Quasiperiodic infinite words, Bull. Eur. Assoc. Theor. Comput. Sci. (EATCS)82 (2004) 170–174.  
  86. F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. Theor. Inform. Appl.26 (1992) 199–204.  
  87. F. Mignosi and P. Séébold, Morphismes Sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux5 (1993) 221–233.  
  88. F. Mignosi and L.Q. Zamboni, On the number of Arnoux-Rauzy words. Acta Arith.101 (2002) 121–129.  
  89. T. Monteil, Illumination dans les billards polygonaux et dynamique symbolique. Ph.D. thesis, Université de la Méditerranée, Faculté des Sciences de Luminy, December (2005).  
  90. T. Monteil and S. Marcus, Quasiperiodic infinite words: multi-scale case and dynamical properties. Theoret. Comput. Sci., to appear, v1.  URIarXiv:math/0603354
  91. M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math.62 (1940) 1–42.  
  92. G. Paquin and L. Vuillon, A characterization of balanced episturmian sequences. Electr. J. Combin.14 (2007) 12.  
  93. G. Pirillo, Inequalities characterizing standard Sturmian words. Pure Math. Appl.14 (2003) 141–144.  
  94. G. Pirillo, Inequalities characterizing standard Sturmian and episturmian words. Theoret. Comput. Sci.341 (2005) 276–292.  
  95. G. Pirillo, Morse and Hedlund's skew Sturmian words revisited. Ann. Comb.12 (2008) 115–121.  
  96. N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, Vol. 1794 of Lect. Notes Math. Springer-Verlag, Berlin (2002).  
  97. G. Rauzy, Suites à termes dans un alphabet fini, in Sémin. Théorie des Nombres, Exp. No. 25, p. 16. Univ. Bordeaux I, Talence, 1982–1983.  
  98. G. Rauzy, Mots infinis en arithmétique, in Automata On Infinite Words, edited by M. Nivat, D. Perrin. Lect. Notes Comput. Sci.192 (1985) 165–171.  
  99. G. Richomme, Conjugacy and episturmian morphisms. Theoret. Comput. Sci.302 (2003) 1–34.  
  100. G. Richomme, Lyndon morphisms. Bull. Belg. Math. Soc. Simon Stevin10 (2003) 761–785.  
  101. G. Richomme, A local balance property of episturmian words, in: Proceedings of the 11th International Conference on Developments in Language Theory 2007 (DLT '07), July 3–6, Turku, Finland. Lect. Notes Comput. Sci.4588 (2007) 371–381.  
  102. G. Richomme, Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci.380 (2007) 393–400.  
  103. G. Richomme, On morphisms preserving infinite Lyndon words. Discrete Math. Theor. Comput. Sci.9 (2007) 89–108.  
  104. G. Richomme, private communication (2007).  
  105. R.N. Risley and L.Q. Zamboni, A generalization of Sturmian sequences: Combinatorial structure and transcendence. Acta Arith.95 (2000) 167–184.  
  106. A. Siegel, Pure discrete spectrum dynamical systems and periodic tiling associated with a substitution. Ann. Inst. Fourier (Grenoble)54 (2004) 341–381.  
  107. B. Tan and Z.-Y. Wen, Some properties of the Tribonacci sequence. Eur. J. Combin.28 (2007) 1703–1719.  
  108. R. Tijdeman, On complementary triples of Sturmian bisequences. Indag. Math.7 (1996) 419–424.  
  109. R. Tijdeman, Intertwinings of Sturmian sequences. Indag. Math.9 (1998) 113–122.  
  110. R. Tijdeman, Fraenkel's conjecture for six sequences. Discrete Math.222 (2000) 223–234.  
  111. D. Vandeth, Sturmian words and words with a critical exponent. Theoret. Comput. Sci.242 (2000) 283–300.  
  112. P. Veerman, Symbolic dynamics and rotation numbers. Physica A134 (1986) 543–576.  
  113. P. Veerman, Symbolic dynamics of order-preserving orbits. Physica D29 (1987) 191–201.  
  114. L. Vuillon, A characterization of Sturmian words by return words. Eur. J. Combin.22 (2001) 263–275.  
  115. L. Vuillon, Balanced words. Bull. Belg. Math. Soc. Simon Stevin10 (2003) 787–805.  
  116. Z.-X. Wen and Y. Zhang, Some remarks on invertible substitutions on three letter alphabet. Chinese Sci. Bull.44 (1999) 1755–1760.  
  117. N. Wozny and L.Q. Zamboni, Frequencies of factors in Arnoux-Rauzy sequences. Acta Arith.96 (2001) 261–278.  
  118. 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), pp. 347–373.  
  119. L.Q. Zamboni, Une généralisation du théorème de Lagrange sur le développement en fraction continue. C.R. Acad. Sci. Paris Sér. I Math.327 (1998) 527–530.  

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.