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.
Keywords: 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, Volume 43 (2009) no. 3, pp. 403-442. doi : 10.1051/ita/2009003. http://archive.numdam.org/articles/10.1051/ita/2009003/
[1] Balances for fixed points of primitive substitutions. Theoret. Comput. Sci. 307 (2003) 47-75. | MR | Zbl
,[2] Palindromic continued fractions. Ann. Inst. Fourier (Grenoble) 57 (2007) 1557-1574. | Numdam | MR | Zbl
and ,[3] Transcendence measure for continued fractions involving repetitive or symmetric patterns. J. Eur. Math. Soc., to appear.
and ,[4] Three distance theorems and combinatorics on words. Enseign. Math. 44 (1998) 103-132. | MR | Zbl
and ,[5] Extremal properties of (epi)sturmian sequences and distribution modulo , in preparation.
and ,[6] Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, UK (2003). | MR | Zbl
and ,[7] Transcendence of Sturmian or morphic continued fractions. J. Number Theory 91 (2001) 39-66. | MR | Zbl
, , and ,[8] Palindromic complexity of infinite words associated with simple Parry numbers. Ann. Inst. Fourier (Grenoble) 56 (2006) 2131-2160. | Numdam | MR | Zbl
, , and ,[9] 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
and ,[10] Efficient detection of quasiperiodicities in strings. Theoret. Comput. Sci. 119 (1993) 247-265. | MR | Zbl
and ,[11] Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 181-207. | MR | Zbl
and ,[12] Représentation géométrique de suites de complexité . Bull. Soc. Math. France 119 (1991) 199-215. | Numdam | MR | Zbl
and ,[13] Complexity of trajectories in rectangular billiards. Commun. Math. Phys. 174 (1995) 43-56. | MR | Zbl
,[14] On the index of Sturmian words, in: Jewels Are Forever. Springer-Verlag, Berlin (1999), pp. 287-294. | MR | Zbl
,[15] Recent results on extensions of Sturmian words. Int. J. Algebra Comput. 12 (2002) 371-385. | MR | Zbl
,[16] 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
and ,[17] A remark on morphic Sturmian words. Theor. Inform. Appl. 28 (1994) 255-263. | Numdam | MR | Zbl
and ,[18] Coding rotations on intervals. Theoret. Comput. Sci. 281 (2002) 99-107. | MR | Zbl
and ,[19] Fréquences des facteurs des suites sturmiennes. Theoret. Comput. Sci. 165 (1996) 295-309. | MR | Zbl
,[20] Autour du système de numération d'Ostrowski. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 209-239. | MR | Zbl
,[21] 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
, and ,[22] Initial powers of Sturmian sequences. Acta Arith. 122 (2006) 315-347. | MR | Zbl
, and ,[23] On substitution invariant Sturmian words: an application of Rauzy fractals. Theoret. Inform. Appl. 41 (2007) 329-349. | Numdam | MR | Zbl
, , and ,[24] Quelques mots sur la droite projective réelle. J. Théor. Nombres Bordeaux 5 (1993) 23-51. | Numdam | MR | Zbl
and ,[25] Palindromic factors of billiard words. Theoret. Comput. Sci. 340 (2005) 334-348. | MR | Zbl
and ,[26] On the palindromic complexity of infinite words. Internat. J. Found. Comput. Sci. 15 (2004) 293-306. | MR | Zbl
, , and ,[27] On some problems related to palindrome closure. RAIRO-Theor. Inf. Appl. 42 (2008) 679-700. | Numdam | MR | Zbl
, , and ,[28] On different generalizations of episturmian words. Theoret. Comput. Sci. 393 (2008) 23-36. | MR | Zbl
, , and ,[29] A connection between palindromic and factor complexity using return words, Adv. in Appl. Math. 42 (2009) 60-74. | MR | Zbl
, , and ,[30] A new characteristic property of rich words. Theoret. Comput. Sci. (in press), doi:10.1016/j.tcs.2008.11.001. | Zbl
, , and ,[31] Sequences with grouped factors, in Developments in Language Theory III. Aristotle University of Thessaloniki, 1998, pp. 211-222.
,[32] 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
and ,[33] Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier (Grenoble) 50 (2000) 1265-1276. | Numdam | MR | Zbl
, and ,[34] Fine and Wilf's theorem for three periods and a generalization of Sturmian words. Theoret. Comput. Sci. 218 (1999) 83-94. | MR | Zbl
, and ,[35] 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
, and ,[36] Sequences with minimal block growth II. Math. Syst. Theor. 8 (1974) 376-382. | MR | Zbl
,[37] Sequences with minimal block growth. Math. Syst. Theor. 7 (1973) 138-153. | MR | Zbl
and ,[38] Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux 5 (1993) 123-137. | Numdam | MR | Zbl
, , and ,[39] The index of Sturmian sequences. Eur. J. Combin. 23 (2002) 23-29. | MR | Zbl
and ,[40] Combinatorial properties of Arnoux-Rauzy subshifts and applications to Schrödinger operators. Rev. Math. Phys. 15 (2003) 745-763. | MR | Zbl
and ,[41] Sturmian words: structure. combinatorics and their arithmetics. Theoret. Comput. Sci. 183 (1997) 45-82. | MR | Zbl
,[42] Rich, Sturmian, and trapezoidal words. Theoret. Comput. Sci. 407 (2008) 569-573. | MR | Zbl
, and ,[43] Palindromes and Sturmian words. Theoret. Comput. Sci. 223 (1999) 73-85. | MR | Zbl
and ,[44] Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001) 539-553. | MR | Zbl
, and ,[45] A characterization of substitutive sequences using return words. Discrete Math. 179 (1998) 89-101. | MR | Zbl
,[46] A generalization of Cobham's theorem. Theor. Comput. Syst. 31 (1998) 169-185. | MR | Zbl
,[47] Linearly recurrent subshifts have a finite number of non-periodic subshift factors. Ergod. Theor. Dyn. Syst. 19 (1999) 953-993. | MR | Zbl
,[48] A little more about morphic Sturmian words. RAIRO-Theor. Inf. Appl. 40 (2006) 511-518. | Numdam | MR | Zbl
,[49] Generalized balances in Sturmian words. Discrete Appl. Math. 121 (2002) 83-101. | MR | Zbl
and ,[50] Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145-154. | MR | Zbl
,[51] Transcendence of numbers with a low complexity expansion. J. Number Theory 67 (1997) 146-161. | MR | Zbl
and ,[52] Substitutional dynamical systems: algebraic characterization of eigenvalues. Ann. Sci. École Norm. Sup. 29 (1995) 519-533. | Numdam | MR | Zbl
, and ,[53] Structure of three interval exchange transformations I. An arithmetic study. Ann. Inst. Fourier (Grenoble) 51 (2001) 861-901. | Numdam | MR | Zbl
, and ,[54] Palindromic prefixes and episturmian words. J. Comb. Th. (A) 113 (2006) 1281-1304. | MR | Zbl
,[55] Palindromic prefixes and diophantine approximation. Monatsh. Math. 151 (2007) 11-37. | MR | Zbl
,[56] Complementing and exactly covering sequences. J. Comb. Th. (A) 14 (1973) 8-20. | MR | Zbl
,[57] On Sturmian and episturmian words, and related topics, Ph.D. Thesis. The University of Adelaide, Australia, April (2006). | Zbl
,[58] Order and quasiperiodicity in episturmian words17-21, (2007) 144-158.
,[59] Powers in a class of -strict standard episturmian words. Theoret. Comput. Sci. 380 (2007) 330-354. | Zbl
,[60] A characterization of fine words over a finite alphabet. Theoret. Comput. Sci. 391 (2008) 51-60. | Zbl
,[61] Characterizations of finite and infinite episturmian words via lexicographic orderings. Eur. J. Combin. 29 (2008) 45-58. | Zbl
, and ,[62] Quasiperiodic and Lyndon episturmian words. Theoret. Comput. Sci. 409 (2008) 578-600. | Zbl
, and ,[63] Palindromic richness. Eur. J. Combin. 30 (2009) 510-531. | Zbl
, , and ,[64] Directive words of episturmian words: equivalences and normalization. RAIRO-Theor. Inf. Appl. 43 (2009) 299-319. | Numdam | MR | Zbl
, and ,[65] Représentation par des transvections des groupes dartin-tits. Group, Geometry and Dynamics 1 (2007) 111-133. | MR | Zbl
,[66] Characterisation of asymptotically Sturmian sequences. Publ. Math. Debrecen 56 (2000) 415-430. | MR | Zbl
and ,[67] Descendants of primitive substitutions. Theor. Comput. Syst. 32 (1999) 133-157. | MR | Zbl
and ,[68] Suites équilibrés. Theoret. Comput. Sci. 242 (2000) 91-108. | MR | Zbl
,[69] Characterisations of balanced words via orderings. Theoret. Comput. Sci 310 (2004) 247-271. | MR | Zbl
and ,[70] On a paper by Castelli, Mignosi, Restivo. RAIRO-Theor. Inf. Appl. 34 (2000) 373-377. | Numdam | MR | Zbl
,[71] Episturmian morphisms and a Galois theorem on continued fractions. RAIRO-Theor. Inf. Appl. 39 (2005) 207-215. | Numdam | MR | Zbl
,[72] Fractional powers in Sturmian words. Theoret. Comput. Sci. 255 (2001) 363-376. | MR | Zbl
and ,[73] Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281-313. | MR | Zbl
and ,[74] On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl. 36 (2002) 385-388. | Numdam | MR | Zbl
and ,[75] Episturmian words: shifts, morphisms and numeration systems. Internat. J. Found. Comput. Sci. 15 (2004) 329-348. | MR | Zbl
and ,[76] Return words in Sturmian and episturmian words. RAIRO-Theor. Inf. Appl. 34 (2000) 343-356. | Numdam | MR | Zbl
and ,[77] Substitution invariant Beatty sequences. Jpn J. Math. 22 (1996) 349-354. | MR | Zbl
and ,[78] On stabilizers of infinite words. Theoret. Comput. Sci. 400 (2008) 169-181. | MR | Zbl
,[79] Quasiperiodic infinite words: some answers. Bull. Eur. Assoc. Theor. Comput. Sci. 84 (2004) 128-138. | MR | Zbl
and ,[80] Quasiperiodic episturmian words17-21, 2007, pp. 201-211.
and ,[81] Quasiperiodic Sturmian words and morphisms. Theoret. Comput. Sci. 372 (2007) 15-25. | MR | Zbl
and ,[82] Combinatorics on Words, Vol. 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, Massachusetts (1983). | MR | Zbl
,[83] Algebraic Combinatorics on Words, Vol. 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, UK, (2002). | MR | Zbl
,[84] Applied Combinatorics on Words, Vol. 105 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, UK, (2005). | MR | Zbl
,[85] Quasiperiodic infinite words, Bull. Eur. Assoc. Theor. Comput. Sci. (EATCS) 82 (2004) 170-174. | MR | Zbl
,[86] Repetitions in the Fibonacci infinite word. Theor. Inform. Appl. 26 (1992) 199-204. | Numdam | MR | Zbl
and ,[87] Morphismes Sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux 5 (1993) 221-233. | Numdam | MR | Zbl
and ,[88] On the number of Arnoux-Rauzy words. Acta Arith. 101 (2002) 121-129. | MR | Zbl
and ,[89] 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] Quasiperiodic infinite words: multi-scale case and dynamical properties. Theoret. Comput. Sci., to appear, arXiv:math/0603354v1. | MR
and ,[91] Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM | MR
and ,[92] A characterization of balanced episturmian sequences. Electr. J. Combin. 14 (2007) 12. | MR | Zbl
and ,[93] Inequalities characterizing standard Sturmian words. Pure Math. Appl. 14 (2003) 141-144. | MR | Zbl
,[94] Inequalities characterizing standard Sturmian and episturmian words. Theoret. Comput. Sci. 341 (2005) 276-292. | MR | Zbl
,[95] Morse and Hedlund's skew Sturmian words revisited. Ann. Comb. 12 (2008) 115-121. | MR
,[96] Substitutions in Dynamics, Arithmetics and Combinatorics, Vol. 1794 of Lect. Notes Math. Springer-Verlag, Berlin (2002). | MR | Zbl
,[97] 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] 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] Conjugacy and episturmian morphisms. Theoret. Comput. Sci. 302 (2003) 1-34. | MR | Zbl
,[100] Lyndon morphisms. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 761-785. | MR | Zbl
,[101] 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] Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci. 380 (2007) 393-400. | MR | Zbl
,[103] On morphisms preserving infinite Lyndon words. Discrete Math. Theor. Comput. Sci. 9 (2007) 89-108. | MR | Zbl
,[104] private communication (2007).
,[105] A generalization of Sturmian sequences: Combinatorial structure and transcendence. Acta Arith. 95 (2000) 167-184. | MR | Zbl
and ,[106] Pure discrete spectrum dynamical systems and periodic tiling associated with a substitution. Ann. Inst. Fourier (Grenoble) 54 (2004) 341-381. | Numdam | MR | Zbl
,[107] Some properties of the Tribonacci sequence. Eur. J. Combin. 28 (2007) 1703-1719. | MR | Zbl
and ,[108] On complementary triples of Sturmian bisequences. Indag. Math. 7 (1996) 419-424. | MR | Zbl
,[109] Intertwinings of Sturmian sequences. Indag. Math. 9 (1998) 113-122. | MR | Zbl
,[110] Fraenkel's conjecture for six sequences. Discrete Math. 222 (2000) 223-234. | MR | Zbl
,[111] Sturmian words and words with a critical exponent. Theoret. Comput. Sci. 242 (2000) 283-300. | MR | Zbl
,[112] Symbolic dynamics and rotation numbers. Physica A 134 (1986) 543-576. | MR | Zbl
,[113] Symbolic dynamics of order-preserving orbits. Physica D 29 (1987) 191-201. | MR | Zbl
,[114] A characterization of Sturmian words by return words. Eur. J. Combin. 22 (2001) 263-275. | MR | Zbl
,[115] Balanced words. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 787-805. | MR | Zbl
,[116] Some remarks on invertible substitutions on three letter alphabet. Chinese Sci. Bull. 44 (1999) 1755-1760. | MR | Zbl
and ,[117] Frequencies of factors in Arnoux-Rauzy sequences. Acta Arith. 96 (2001) 261-278. | MR | Zbl
and ,[118] 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] 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
,Cited by Sources: