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.
@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},
volume = {43},
year = {2009},
pages = {403-442},
doi = {10.1051/ita/2009003},
mrnumber = {2541129},
zbl = {pre05578831},
language = {en},
url = {http://dml.mathdoc.fr/item/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) pp. 403-442. doi : 10.1051/ita/2009003. http://gdmltest.u-ga.fr/item/ITA_2009__43_3_403_0/
[1] , Balances for fixed points of primitive substitutions. Theoret. Comput. Sci. 307 (2003) 47-75. | MR 2014730 | Zbl 1059.68083
[2] and , Palindromic continued fractions. Ann. Inst. Fourier (Grenoble) 57 (2007) 1557-1574. | Numdam | MR 2364142 | Zbl 1126.11036
[3] and , Transcendence measure for continued fractions involving repetitive or symmetric patterns. J. Eur. Math. Soc., to appear.
[4] and , Three distance theorems and combinatorics on words. Enseign. Math. 44 (1998) 103-132. | MR 1643286 | Zbl 0997.11051
[5] and , Extremal properties of (epi)sturmian sequences and distribution modulo , in preparation.
[6] and , Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, UK (2003). | MR 1997038 | Zbl 1086.11015
[7] , , and , Transcendence of Sturmian or morphic continued fractions. J. Number Theory 91 (2001) 39-66. | MR 1869317 | Zbl 0998.11036
[8] , , and , Palindromic complexity of infinite words associated with simple Parry numbers. Ann. Inst. Fourier (Grenoble) 56 (2006) 2131-2160. | Numdam | MR 2290777 | Zbl 1121.68089
[9] and , String pattern matching for a deluge survival kit, in: Handbook of Massive Data Sets, Massive Comput., Vol. 4. Kluwer Acad. Publ., Dordrecht (2002). | MR 1965528 | Zbl 1021.68029
[10] and , Efficient detection of quasiperiodicities in strings. Theoret. Comput. Sci. 119 (1993) 247-265. | MR 1244293 | Zbl 0804.68109
[11] and , Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 181-207. | MR 1838930 | Zbl 1007.37001
[12] and , Représentation géométrique de suites de complexité . Bull. Soc. Math. France 119 (1991) 199-215. | Numdam | MR 1116845 | Zbl 0789.28011
[13] , Complexity of trajectories in rectangular billiards. Commun. Math. Phys. 174 (1995) 43-56. | MR 1372799 | Zbl 0839.11006
[14] , On the index of Sturmian words, in: Jewels Are Forever. Springer-Verlag, Berlin (1999), pp. 287-294. | MR 1719097 | Zbl 0982.11010
[15] , Recent results on extensions of Sturmian words. Int. J. Algebra Comput. 12 (2002) 371-385. | MR 1902372 | Zbl 1007.68141
[16] and , 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 1265070 | Zbl 0925.11026
[17] and , A remark on morphic Sturmian words. Theor. Inform. Appl. 28 (1994) 255-263. | Numdam | MR 1282447 | Zbl 0883.68104
[18] and , Coding rotations on intervals. Theoret. Comput. Sci. 281 (2002) 99-107. | MR 1909570 | Zbl 0997.68094
[19] , Fréquences des facteurs des suites sturmiennes. Theoret. Comput. Sci. 165 (1996) 295-309. | MR 1411889 | Zbl 0872.11018
[20] , Autour du système de numération d'Ostrowski. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 209-239. | MR 1838931 | Zbl 0994.68100
[21] , and , 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 2180244 | Zbl 1156.37301
[22] , and , Initial powers of Sturmian sequences. Acta Arith. 122 (2006) 315-347. | MR 2234421 | Zbl 1117.37005
[23] , , and , On substitution invariant Sturmian words: an application of Rauzy fractals. Theoret. Inform. Appl. 41 (2007) 329-349. | Numdam | MR 2354361 | Zbl 1140.11014
[24] and , Quelques mots sur la droite projective réelle. J. Théor. Nombres Bordeaux 5 (1993) 23-51. | Numdam | MR 1251226 | Zbl 0839.11008
[25] and , Palindromic factors of billiard words. Theoret. Comput. Sci. 340 (2005) 334-348. | MR 2150758 | Zbl 1078.68113
[26] , , and , On the palindromic complexity of infinite words. Internat. J. Found. Comput. Sci. 15 (2004) 293-306. | MR 2071459 | Zbl 1067.68113
[27] , , and , On some problems related to palindrome closure. RAIRO-Theor. Inf. Appl. 42 (2008) 679-700. | Numdam | MR 2458701 | Zbl 1155.68061
[28] , , and , On different generalizations of episturmian words. Theoret. Comput. Sci. 393 (2008) 23-36. | MR 2397238 | Zbl 1136.68045
[29] , , and , A connection between palindromic and factor complexity using return words, Adv. in Appl. Math. 42 (2009) 60-74. | MR 2475313 | Zbl 1160.68027
[30] , , and , A new characteristic property of rich words. Theoret. Comput. Sci. (in press), doi:10.1016/j.tcs.2008.11.001. | Zbl 1173.68048
[31] , Sequences with grouped factors, in Developments in Language Theory III. Aristotle University of Thessaloniki, 1998, pp. 211-222.
[32] and , 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 2290780 | Zbl 1138.68045
[33] , and , Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier (Grenoble) 50 (2000) 1265-1276. | Numdam | MR 1799745 | Zbl 1004.37008
[34] , and , Fine and Wilf's theorem for three periods and a generalization of Sturmian words. Theoret. Comput. Sci. 218 (1999) 83-94. | MR 1687764 | Zbl 0916.68114
[35] , and , Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci. J. Théor. Nombres Bordeaux 13 (2001) 371-394. | Numdam | MR 1879664 | Zbl 1038.37010
[36] , Sequences with minimal block growth II. Math. Syst. Theor. 8 (1974) 376-382. | MR 391053 | Zbl 0299.54032
[37] and , Sequences with minimal block growth. Math. Syst. Theor. 7 (1973) 138-153. | MR 322838 | Zbl 0256.54028
[38] , , and , Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux 5 (1993) 123-137. | Numdam | MR 1251232 | Zbl 0786.11041
[39] and , The index of Sturmian sequences. Eur. J. Combin. 23 (2002) 23-29. | MR 1878771 | Zbl 1002.11020
[40] and , Combinatorial properties of Arnoux-Rauzy subshifts and applications to Schrödinger operators. Rev. Math. Phys. 15 (2003) 745-763. | MR 2018286 | Zbl 1081.81521
[41] , Sturmian words: structure. combinatorics and their arithmetics. Theoret. Comput. Sci. 183 (1997) 45-82. | MR 1468450 | Zbl 0911.68098
[42] , and , Rich, Sturmian, and trapezoidal words. Theoret. Comput. Sci. 407 (2008) 569-573. | MR 2463038 | Zbl 1153.68045
[43] and , Palindromes and Sturmian words. Theoret. Comput. Sci. 223 (1999) 73-85. | MR 1704637 | Zbl 0930.68116
[44] , and , Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001) 539-553. | MR 1819089 | Zbl 0981.68126
[45] , A characterization of substitutive sequences using return words. Discrete Math. 179 (1998) 89-101. | MR 1489074 | Zbl 0895.68087
[46] , A generalization of Cobham's theorem. Theor. Comput. Syst. 31 (1998) 169-185. | MR 1491657 | Zbl 0895.68081
[47] , Linearly recurrent subshifts have a finite number of non-periodic subshift factors. Ergod. Theor. Dyn. Syst. 19 (1999) 953-993. | MR 1779393 | Zbl 1044.46543
[48] , A little more about morphic Sturmian words. RAIRO-Theor. Inf. Appl. 40 (2006) 511-518. | Numdam | MR 2269208 | Zbl 1110.68118
[49] and , Generalized balances in Sturmian words. Discrete Appl. Math. 121 (2002) 83-101. | MR 1907548 | Zbl 1002.68117
[50] , Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145-154. | MR 1665394 | Zbl 0936.37008
[51] and , Transcendence of numbers with a low complexity expansion. J. Number Theory 67 (1997) 146-161. | MR 1486494 | Zbl 0895.11029
[52] , and , Substitutional dynamical systems: algebraic characterization of eigenvalues. Ann. Sci. École Norm. Sup. 29 (1995) 519-533. | Numdam | MR 1386224 | Zbl 0866.11023
[53] , and , Structure of three interval exchange transformations I. An arithmetic study. Ann. Inst. Fourier (Grenoble) 51 (2001) 861-901. | Numdam | MR 1849209 | Zbl 1029.11036
[54] , Palindromic prefixes and episturmian words. J. Comb. Th. (A) 113 (2006) 1281-1304. | MR 2259061 | Zbl 1109.68082
[55] , Palindromic prefixes and diophantine approximation. Monatsh. Math. 151 (2007) 11-37. | MR 2317388 | Zbl 1124.11032
[56] , Complementing and exactly covering sequences. J. Comb. Th. (A) 14 (1973) 8-20. | MR 309770 | Zbl 0257.05023
[57] , On Sturmian and episturmian words, and related topics, Ph.D. Thesis. The University of Adelaide, Australia, April (2006). | Zbl 1102.68516
[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 1119.68140
[60] , A characterization of fine words over a finite alphabet. Theoret. Comput. Sci. 391 (2008) 51-60. | Zbl 1133.68065
[61] , and , Characterizations of finite and infinite episturmian words via lexicographic orderings. Eur. J. Combin. 29 (2008) 45-58. | Zbl 1131.68076
[62] , and , Quasiperiodic and Lyndon episturmian words. Theoret. Comput. Sci. 409 (2008) 578-600. | Zbl 1155.68065
[63] , , and , Palindromic richness. Eur. J. Combin. 30 (2009) 510-531. | Zbl 1169.68040
[64] , and , Directive words of episturmian words: equivalences and normalization. RAIRO-Theor. Inf. Appl. 43 (2009) 299-319. | Numdam | MR 2512261 | Zbl 1166.68034
[65] , Représentation par des transvections des groupes dartin-tits. Group, Geometry and Dynamics 1 (2007) 111-133. | MR 2319454 | Zbl 1151.20031
[66] and , Characterisation of asymptotically Sturmian sequences. Publ. Math. Debrecen 56 (2000) 415-430. | MR 1765990 | Zbl 0961.11004
[67] and , Descendants of primitive substitutions. Theor. Comput. Syst. 32 (1999) 133-157. | MR 1663912 | Zbl 0916.68086
[68] , Suites équilibrés. Theoret. Comput. Sci. 242 (2000) 91-108. | MR 1769142 | Zbl 0944.68149
[69] and , Characterisations of balanced words via orderings. Theoret. Comput. Sci 310 (2004) 247-271. | MR 2020344 | Zbl 1071.68090
[70] , On a paper by Castelli, Mignosi, Restivo. RAIRO-Theor. Inf. Appl. 34 (2000) 373-377. | Numdam | MR 1829233 | Zbl 0987.68056
[71] , Episturmian morphisms and a Galois theorem on continued fractions. RAIRO-Theor. Inf. Appl. 39 (2005) 207-215. | Numdam | MR 2132588 | Zbl 1126.68519
[72] and , Fractional powers in Sturmian words. Theoret. Comput. Sci. 255 (2001) 363-376. | MR 1819081 | Zbl 0974.68159
[73] and , Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281-313. | MR 1896357 | Zbl 1002.68116
[74] and , On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl. 36 (2002) 385-388. | Numdam | MR 1965423 | Zbl 1060.68094
[75] and , Episturmian words: shifts, morphisms and numeration systems. Internat. J. Found. Comput. Sci. 15 (2004) 329-348. | MR 2071462 | Zbl 1067.68115
[76] and , Return words in Sturmian and episturmian words. RAIRO-Theor. Inf. Appl. 34 (2000) 343-356. | Numdam | MR 1829231 | Zbl 0987.68055
[77] and , Substitution invariant Beatty sequences. Jpn J. Math. 22 (1996) 349-354. | MR 1432380 | Zbl 0868.11015
[78] , On stabilizers of infinite words. Theoret. Comput. Sci. 400 (2008) 169-181. | MR 2424350 | Zbl 1145.68042
[79] and , Quasiperiodic infinite words: some answers. Bull. Eur. Assoc. Theor. Comput. Sci. 84 (2004) 128-138. | MR 2132859 | Zbl 1169.68566
[80] and , Quasiperiodic episturmian words17-21, 2007, pp. 201-211.
[81] and , Quasiperiodic Sturmian words and morphisms. Theoret. Comput. Sci. 372 (2007) 15-25. | MR 2299022 | Zbl 1108.68097
[82] , Combinatorics on Words, Vol. 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, Massachusetts (1983). | MR 675953 | Zbl 0514.20045
[83] , Algebraic Combinatorics on Words, Vol. 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, UK, (2002). | MR 1905123 | Zbl 1001.68093
[84] , Applied Combinatorics on Words, Vol. 105 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, UK, (2005). | MR 2165687 | Zbl 1133.68067
[85] , Quasiperiodic infinite words, Bull. Eur. Assoc. Theor. Comput. Sci. (EATCS) 82 (2004) 170-174. | MR 2132620 | Zbl 1169.68484
[86] and , Repetitions in the Fibonacci infinite word. Theor. Inform. Appl. 26 (1992) 199-204. | Numdam | MR 1170322 | Zbl 0761.68078
[87] and , Morphismes Sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux 5 (1993) 221-233. | Numdam | MR 1265903 | Zbl 0797.11029
[88] and , On the number of Arnoux-Rauzy words. Acta Arith. 101 (2002) 121-129. | MR 1880303 | Zbl 1005.68117
[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] and , Quasiperiodic infinite words: multi-scale case and dynamical properties. Theoret. Comput. Sci., to appear, arXiv:math/0603354v1. | MR 2132620
[91] and , Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM 66.0188.03 | MR 745
[92] and , A characterization of balanced episturmian sequences. Electr. J. Combin. 14 (2007) 12. | MR 2302540 | Zbl 1121.68091
[93] , Inequalities characterizing standard Sturmian words. Pure Math. Appl. 14 (2003) 141-144. | MR 2054742 | Zbl 1065.68081
[94] , Inequalities characterizing standard Sturmian and episturmian words. Theoret. Comput. Sci. 341 (2005) 276-292. | MR 2159654 | Zbl 1077.68085
[95] , Morse and Hedlund's skew Sturmian words revisited. Ann. Comb. 12 (2008) 115-121. | MR 2401140 | Zbl pre05313034
[96] , Substitutions in Dynamics, Arithmetics and Combinatorics, Vol. 1794 of Lect. Notes Math. Springer-Verlag, Berlin (2002). | MR 1970385 | Zbl 1014.11015
[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 750326 | Zbl 0547.10048
[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 814741 | Zbl 0613.10044
[99] , Conjugacy and episturmian morphisms. Theoret. Comput. Sci. 302 (2003) 1-34. | MR 1981940 | Zbl 1044.68142
[100] , Lyndon morphisms. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 761-785. | MR 2073025 | Zbl 1101.68075
[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 2380446 | Zbl pre05215389
[102] , Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci. 380 (2007) 393-400. | MR 2331008 | Zbl 1118.68111
[103] , On morphisms preserving infinite Lyndon words. Discrete Math. Theor. Comput. Sci. 9 (2007) 89-108. | MR 2306522 | Zbl 1152.68490
[104] , private communication (2007).
[105] and , A generalization of Sturmian sequences: Combinatorial structure and transcendence. Acta Arith. 95 (2000) 167-184. | MR 1785413 | Zbl 0953.11007
[106] , Pure discrete spectrum dynamical systems and periodic tiling associated with a substitution. Ann. Inst. Fourier (Grenoble) 54 (2004) 341-381. | Numdam | MR 2073838 | Zbl 1083.37009
[107] and , Some properties of the Tribonacci sequence. Eur. J. Combin. 28 (2007) 1703-1719. | MR 2339496 | Zbl 1120.11009
[108] , On complementary triples of Sturmian bisequences. Indag. Math. 7 (1996) 419-424. | MR 1621393 | Zbl 0862.68085
[109] , Intertwinings of Sturmian sequences. Indag. Math. 9 (1998) 113-122. | MR 1618219 | Zbl 0918.11012
[110] , Fraenkel's conjecture for six sequences. Discrete Math. 222 (2000) 223-234. | MR 1771401 | Zbl 1101.11314
[111] , Sturmian words and words with a critical exponent. Theoret. Comput. Sci. 242 (2000) 283-300. | MR 1769782 | Zbl 0944.68148
[112] , Symbolic dynamics and rotation numbers. Physica A 134 (1986) 543-576. | MR 861742 | Zbl 0655.58019
[113] , Symbolic dynamics of order-preserving orbits. Physica D 29 (1987) 191-201. | MR 923891 | Zbl 0625.28012
[114] , A characterization of Sturmian words by return words. Eur. J. Combin. 22 (2001) 263-275. | MR 1808196 | Zbl 0968.68124
[115] , Balanced words. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 787-805. | MR 2073026 | Zbl 1070.68129
[116] and , Some remarks on invertible substitutions on three letter alphabet. Chinese Sci. Bull. 44 (1999) 1755-1760. | MR 1737516 | Zbl 1040.20504
[117] and , Frequencies of factors in Arnoux-Rauzy sequences. Acta Arith. 96 (2001) 261-278. | MR 1814281 | Zbl 0973.11030
[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 1738827 | Zbl 0971.11007
[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 1647296 | Zbl 1039.11500