Episturmian words : a survey

Glen, Amy; Justin, Jacques

doi:10.1051/ita/2009003

Glen, Amy ; Justin, Jacques

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 3, pp. 403-442.

Résumé

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.

MR | 1 citation dans Numdam

DOI : 10.1051/ita/2009003

Classification : 68R15
Mots-clés : combinatorics on words, episturmian words, Arnoux-Rauzy sequences, sturmian words, episturmian morphisms

@article{ITA_2009__43_3_403_0,
     author = {Glen, Amy and Justin, Jacques},
     title = {Episturmian words : a survey},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {403--442},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {3},
     year = {2009},
     doi = {10.1051/ita/2009003},
     mrnumber = {2541129},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2009003/}
}

TY  - JOUR
AU  - Glen, Amy
AU  - Justin, Jacques
TI  - Episturmian words : a survey
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2009
SP  - 403
EP  - 442
VL  - 43
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2009003/
DO  - 10.1051/ita/2009003
LA  - en
ID  - ITA_2009__43_3_403_0
ER  -

%0 Journal Article
%A Glen, Amy
%A Justin, Jacques
%T Episturmian words : a survey
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2009
%P 403-442
%V 43
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2009003/
%R 10.1051/ita/2009003
%G en
%F ITA_2009__43_3_403_0

Glen, Amy; Justin, Jacques. Episturmian words : a survey. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 3, pp. 403-442. doi : 10.1051/ita/2009003. http://archive.numdam.org/articles/10.1051/ita/2009003/

Bibliographie
Cité par

[1] B. Adamczewski, Balances for fixed points of primitive substitutions. Theoret. Comput. Sci. 307 (2003) 47-75. | MR | Zbl

[2] B. Adamczewski and Y. Bugeaud, Palindromic continued fractions. Ann. Inst. Fourier (Grenoble) 57 (2007) 1557-1574. | Numdam | MR | Zbl

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

[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). | MR | Zbl

[7] J.-P. Allouche, J.L. Davison, M. Queffélec and L.Q. Zamboni, Transcendence of Sturmian or morphic continued fractions. J. Number Theory 91 (2001) 39-66. | MR | Zbl

[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. | Numdam | MR | Zbl

[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). | MR | Zbl

[10] A. Apostolico and A. Ehrenfeucht, Efficient detection of quasiperiodicities in strings. Theoret. Comput. Sci. 119 (1993) 247-265. | MR | Zbl

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

[12] P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité $2 n + 1$ . Bull. Soc. Math. France 119 (1991) 199-215. | Numdam | MR | Zbl

[13] Yu. Baryshnikov, Complexity of trajectories in rectangular billiards. Commun. Math. Phys. 174 (1995) 43-56. | MR | Zbl

[14] J. Berstel, On the index of Sturmian words, in: Jewels Are Forever. Springer-Verlag, Berlin (1999), pp. 287-294. | MR | Zbl

[15] J. Berstel, Recent results on extensions of Sturmian words. Int. J. Algebra Comput. 12 (2002) 371-385. | MR | Zbl

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

[17] J. Berstel and P. Séébold, A remark on morphic Sturmian words. Theor. Inform. Appl. 28 (1994) 255-263. | Numdam | MR | Zbl

[18] J. Berstel and L. Vuillon, Coding rotations on intervals. Theoret. Comput. Sci. 281 (2002) 99-107. | MR | Zbl

[19] V. Berthé, Fréquences des facteurs des suites sturmiennes. Theoret. Comput. Sci. 165 (1996) 295-309. | MR | Zbl

[20] V. Berthé, Autour du système de numération d'Ostrowski. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 209-239. | MR | Zbl

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

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

[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. | Numdam | MR | Zbl

[24] J.-P. Borel and F. Laubie, Quelques mots sur la droite projective réelle. J. Théor. Nombres Bordeaux 5 (1993) 23-51. | Numdam | MR | Zbl

[25] J.-P. Borel and C. Reutenauer, Palindromic factors of billiard words. Theoret. Comput. Sci. 340 (2005) 334-348. | MR | Zbl

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

[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. | Numdam | MR | Zbl

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

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

[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:10.1016/j.tcs.2008.11.001. | Zbl

[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. | Numdam | MR | Zbl

[33] J. Cassaigne, S. Ferenczi and L.Q. Zamboni, Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier (Grenoble) 50 (2000) 1265-1276. | Numdam | MR | Zbl

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

[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. | Numdam | MR | Zbl

[36] E.M. Coven, Sequences with minimal block growth II. Math. Syst. Theor. 8 (1974) 376-382. | MR | Zbl

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

[38] D. Crisp, W. Moran, A. Pollington and P. Shiue, Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux 5 (1993) 123-137. | Numdam | MR | Zbl

[39] D. Damanik and D. Lenz, The index of Sturmian sequences. Eur. J. Combin. 23 (2002) 23-29. | MR | Zbl

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

[41] A. De Luca, Sturmian words: structure. combinatorics and their arithmetics. Theoret. Comput. Sci. 183 (1997) 45-82. | MR | Zbl

[42] A. De Luca, A. Glen and L.Q. Zamboni, Rich, Sturmian, and trapezoidal words. Theoret. Comput. Sci. 407 (2008) 569-573. | MR | Zbl

[43] X. Droubay and G. Pirillo, Palindromes and Sturmian words. Theoret. Comput. Sci. 223 (1999) 73-85. | MR | Zbl

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

[45] F. Durand, A characterization of substitutive sequences using return words. Discrete Math. 179 (1998) 89-101. | MR | Zbl

[46] F. Durand, A generalization of Cobham's theorem. Theor. Comput. Syst. 31 (1998) 169-185. | MR | Zbl

[47] F. Durand, Linearly recurrent subshifts have a finite number of non-periodic subshift factors. Ergod. Theor. Dyn. Syst. 19 (1999) 953-993. | MR | Zbl

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

[49] I. Fagnot and L. Vuillon, Generalized balances in Sturmian words. Discrete Appl. Math. 121 (2002) 83-101. | MR | Zbl

[50] S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145-154. | MR | Zbl

[51] S. Ferenczi and C. Mauduit, Transcendence of numbers with a low complexity expansion. J. Number Theory 67 (1997) 146-161. | MR | Zbl

[52] S. Ferenczi, C. Mauduit and A. Nogueira, Substitutional dynamical systems: algebraic characterization of eigenvalues. Ann. Sci. École Norm. Sup. 29 (1995) 519-533. | Numdam | MR | Zbl

[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. | Numdam | MR | Zbl

[54] S. Fischler, Palindromic prefixes and episturmian words. J. Comb. Th. (A) 113 (2006) 1281-1304. | MR | Zbl

[55] S. Fischler, Palindromic prefixes and diophantine approximation. Monatsh. Math. 151 (2007) 11-37. | MR | Zbl

[56] A.S. Fraenkel, Complementing and exactly covering sequences. J. Comb. Th. (A) 14 (1973) 8-20. | MR | Zbl

[57] A. Glen, On Sturmian and episturmian words, and related topics, Ph.D. Thesis. The University of Adelaide, Australia, April (2006). | Zbl

[58] A. Glen, Order and quasiperiodicity in episturmian words17-21, (2007) 144-158.

[59] A. Glen, Powers in a class of $𝒜$ -strict standard episturmian words. Theoret. Comput. Sci. 380 (2007) 330-354. | Zbl

[60] A. Glen, A characterization of fine words over a finite alphabet. Theoret. Comput. Sci. 391 (2008) 51-60. | Zbl

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

[62] A. Glen, F. Levé and G. Richomme, Quasiperiodic and Lyndon episturmian words. Theoret. Comput. Sci. 409 (2008) 578-600. | Zbl

[63] A. Glen, J. Justin, S. Widmer and L.Q. Zamboni, Palindromic richness. Eur. J. Combin. 30 (2009) 510-531. | Zbl

[64] A. Glen, F. Levé and G. Richomme, Directive words of episturmian words: equivalences and normalization. RAIRO-Theor. Inf. Appl. 43 (2009) 299-319. | Numdam | MR | Zbl

[65] E. Godelle, Représentation par des transvections des groupes dartin-tits. Group, Geometry and Dynamics 1 (2007) 111-133. | MR | Zbl

[66] A. Heinis and R. Tijdeman, Characterisation of asymptotically Sturmian sequences. Publ. Math. Debrecen 56 (2000) 415-430. | MR | Zbl

[67] C. Holton and L.Q. Zamboni, Descendants of primitive substitutions. Theor. Comput. Syst. 32 (1999) 133-157. | MR | Zbl

[68] P. Hubert, Suites équilibrés. Theoret. Comput. Sci. 242 (2000) 91-108. | MR | Zbl

[69] O. Jenkinson and L.Q. Zamboni, Characterisations of balanced words via orderings. Theoret. Comput. Sci 310 (2004) 247-271. | MR | Zbl

[70] J. Justin, On a paper by Castelli, Mignosi, Restivo. RAIRO-Theor. Inf. Appl. 34 (2000) 373-377. | Numdam | MR | Zbl

[71] J. Justin, Episturmian morphisms and a Galois theorem on continued fractions. RAIRO-Theor. Inf. Appl. 39 (2005) 207-215. | Numdam | MR | Zbl

[72] J. Justin and G. Pirillo, Fractional powers in Sturmian words. Theoret. Comput. Sci. 255 (2001) 363-376. | MR | Zbl

[73] J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281-313. | MR | Zbl

[74] J. Justin and G. Pirillo, On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl. 36 (2002) 385-388. | Numdam | MR | Zbl

[75] J. Justin and G. Pirillo, Episturmian words: shifts, morphisms and numeration systems. Internat. J. Found. Comput. Sci. 15 (2004) 329-348. | MR | Zbl

[76] J. Justin and L. Vuillon, Return words in Sturmian and episturmian words. RAIRO-Theor. Inf. Appl. 34 (2000) 343-356. | Numdam | MR | Zbl

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

[78] D. Krieger, On stabilizers of infinite words. Theoret. Comput. Sci. 400 (2008) 169-181. | MR | Zbl

[79] F. Levé and G. Richomme, Quasiperiodic infinite words: some answers. Bull. Eur. Assoc. Theor. Comput. Sci. 84 (2004) 128-138. | MR | Zbl

[80] F. Levé and G. Richomme, Quasiperiodic episturmian words17-21, 2007, pp. 201-211.

[81] F. Levé and G. Richomme, Quasiperiodic Sturmian words and morphisms. Theoret. Comput. Sci. 372 (2007) 15-25. | MR | Zbl

[82] M. Lothaire, Combinatorics on Words, Vol. 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, Massachusetts (1983). | MR | Zbl

[83] M. Lothaire, Algebraic Combinatorics on Words, Vol. 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, UK, (2002). | MR | Zbl

[84] M. Lothaire, Applied Combinatorics on Words, Vol. 105 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, UK, (2005). | MR | Zbl

[85] S. Marcus, Quasiperiodic infinite words, Bull. Eur. Assoc. Theor. Comput. Sci. (EATCS) 82 (2004) 170-174. | MR | Zbl

[86] F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. Theor. Inform. Appl. 26 (1992) 199-204. | Numdam | MR | Zbl

[87] F. Mignosi and P. Séébold, Morphismes Sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux 5 (1993) 221-233. | Numdam | MR | Zbl

[88] F. Mignosi and L.Q. Zamboni, On the number of Arnoux-Rauzy words. Acta Arith. 101 (2002) 121-129. | MR | Zbl

[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, arXiv:math/0603354v1. | MR

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

[92] G. Paquin and L. Vuillon, A characterization of balanced episturmian sequences. Electr. J. Combin. 14 (2007) 12. | MR | Zbl

[93] G. Pirillo, Inequalities characterizing standard Sturmian words. Pure Math. Appl. 14 (2003) 141-144. | MR | Zbl

[94] G. Pirillo, Inequalities characterizing standard Sturmian and episturmian words. Theoret. Comput. Sci. 341 (2005) 276-292. | MR | Zbl

[95] G. Pirillo, Morse and Hedlund's skew Sturmian words revisited. Ann. Comb. 12 (2008) 115-121. | MR

[96] N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, Vol. 1794 of Lect. Notes Math. Springer-Verlag, Berlin (2002). | MR | Zbl

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

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

[99] G. Richomme, Conjugacy and episturmian morphisms. Theoret. Comput. Sci. 302 (2003) 1-34. | MR | Zbl

[100] G. Richomme, Lyndon morphisms. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 761-785. | MR | Zbl

[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. | MR

[102] G. Richomme, Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci. 380 (2007) 393-400. | MR | Zbl

[103] G. Richomme, On morphisms preserving infinite Lyndon words. Discrete Math. Theor. Comput. Sci. 9 (2007) 89-108. | MR | Zbl

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

[106] A. Siegel, Pure discrete spectrum dynamical systems and periodic tiling associated with a substitution. Ann. Inst. Fourier (Grenoble) 54 (2004) 341-381. | Numdam | MR | Zbl

[107] B. Tan and Z.-Y. Wen, Some properties of the Tribonacci sequence. Eur. J. Combin. 28 (2007) 1703-1719. | MR | Zbl

[108] R. Tijdeman, On complementary triples of Sturmian bisequences. Indag. Math. 7 (1996) 419-424. | MR | Zbl

[109] R. Tijdeman, Intertwinings of Sturmian sequences. Indag. Math. 9 (1998) 113-122. | MR | Zbl

[110] R. Tijdeman, Fraenkel's conjecture for six sequences. Discrete Math. 222 (2000) 223-234. | MR | Zbl

[111] D. Vandeth, Sturmian words and words with a critical exponent. Theoret. Comput. Sci. 242 (2000) 283-300. | MR | Zbl

[112] P. Veerman, Symbolic dynamics and rotation numbers. Physica A 134 (1986) 543-576. | MR | Zbl

[113] P. Veerman, Symbolic dynamics of order-preserving orbits. Physica D 29 (1987) 191-201. | MR | Zbl

[114] L. Vuillon, A characterization of Sturmian words by return words. Eur. J. Combin. 22 (2001) 263-275. | MR | Zbl

[115] L. Vuillon, Balanced words. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 787-805. | MR | Zbl

[116] Z.-X. Wen and Y. Zhang, Some remarks on invertible substitutions on three letter alphabet. Chinese Sci. Bull. 44 (1999) 1755-1760. | MR | Zbl

[117] N. Wozny and L.Q. Zamboni, Frequencies of factors in Arnoux-Rauzy sequences. Acta Arith. 96 (2001) 261-278. | MR | Zbl

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

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

Cité par Sources :