Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-28T06:08:42.696Z Has data issue: false hasContentIssue false
  • English
  • Français

Episturmian words: a survey

Published online by Cambridge University Press:  06 March 2009

Amy Glen  and
Jacques Justin
Amy Glen
Affiliation:
LaCIM, Université du Québec à Montréal, C.P. 8888, succursale Centre-ville, Montréal, Québec, H3C 3P8, Canada; The Mathematics Institute, Reykjavik University, Kringlan 1, IS-103 Reykjavik, Iceland; [email protected]
Jacques Justin
Affiliation:
LIAFA, Université Paris Diderot - Paris 7, Case 7014, 75205 Paris Cedex 13, France; [email protected]
Get access

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.

Keywords

Combinatorics on wordsepisturmian wordsArnoux-Rauzy sequencesSturmian wordsepisturmian morphisms.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 43 , Issue 3 , July 2009 , pp. 403 - 442
Copyright
© EDP Sciences, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Adamczewski, B., Balances for fixed points of primitive substitutions. Theoret. Comput. Sci. 307 (2003) 47–75. CrossRef
Adamczewski, B. and Bugeaud, Y., Palindromic continued fractions. Ann. Inst. Fourier (Grenoble) 57 (2007) 1557–1574. CrossRef
B. Adamczewski and Y. Bugeaud, Transcendence measure for continued fractions involving repetitive or symmetric patterns. J. Eur. Math. Soc., to appear.
Alessandri, P. and Berthé, V., Three distance theorems and combinatorics on words. Enseign. Math. 44 (1998) 103–132.
J.-P. Allouche and A. Glen, Extremal properties of (epi)sturmian sequences and distribution modulo 1, in preparation.
J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, UK (2003).
Allouche, J.-P., Davison, J.L., Queffélec, M. and Zamboni, L.Q., Transcendence of Sturmian or morphic continued fractions. J. Number Theory 91 (2001) 39–66. CrossRef
Ambrož, P., Frougny, C., Masáková, Z. and Pelantová, E., Palindromic complexity of infinite words associated with simple Parry numbers. Ann. Inst. Fourier (Grenoble) 56 (2006) 2131–2160. CrossRef
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).
Apostolico, A. and Ehrenfeucht, A., Efficient detection of quasiperiodicities in strings. Theoret. Comput. Sci. 119 (1993) 247–265. CrossRef
Arnoux, P. and Ito, S., Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 181–207.
Arnoux, P. and Rauzy, G., Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France 119 (1991) 199–215. CrossRef
Baryshnikov, Yu., Complexity of trajectories in rectangular billiards. Commun. Math. Phys. 174 (1995) 43–56. CrossRef
J. Berstel, On the index of Sturmian words, in: Jewels Are Forever. Springer-Verlag, Berlin (1999), pp. 287–294.
Berstel, J., Recent results on extensions of Sturmian words. Int. J. Algebra Comput. 12 (2002) 371–385. CrossRef
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.
Berstel, J. and Séébold, P., A remark on morphic Sturmian words. Theor. Inform. Appl. 28 (1994) 255–263. CrossRef
Berstel, J. and Vuillon, L., Coding rotations on intervals. Theoret. Comput. Sci. 281 (2002) 99–107. CrossRef
Berthé, V., Fréquences des facteurs des suites sturmiennes. Theoret. Comput. Sci. 165 (1996) 295–309. CrossRef
Berthé, V., Autour du système de numération d'Ostrowski. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 209–239.
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.
Berthé, V., Holton, C. and Zamboni, L.Q., Initial powers of Sturmian sequences. Acta Arith. 122 (2006) 315–347. CrossRef
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.
Borel, J.-P. and Laubie, F., Quelques mots sur la droite projective réelle. J. Théor. Nombres Bordeaux  5 (1993) 23–51. CrossRef
Borel, J.-P. and Reutenauer, C., Palindromic factors of billiard words. Theoret. Comput. Sci. 340 (2005) 334–348. CrossRef
Brlek, S., Hamel, S., Nivat, M. and Reutenauer, C., On the palindromic complexity of infinite words. Internat. J. Found. Comput. Sci. 15 (2004) 293–306. CrossRef
Bucci, M., de Luca, A., De Luca, A. and Zamboni, L.Q., On some problems related to palindrome closure. RAIRO-Theor. Inf. Appl. 42 (2008) 679-700. CrossRef
Bucci, M., de Luca, A., De Luca, A. and Zamboni, L.Q., On different generalizations of episturmian words. Theoret. Comput. Sci. 393 (2008) 23–36. CrossRef
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.
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.
J. Cassaigne, Sequences with grouped factors, in Developments in Language Theory III. Aristotle University of Thessaloniki, 1998, pp. 211–222.
Cassaigne, J. and Chekhova, N., 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. CrossRef
Cassaigne, J., Ferenczi, S. and Zamboni, L.Q., Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier (Grenoble) 50 (2000) 1265–1276. CrossRef
Castelli, M.G., Mignosi, F. and Restivo, A., Fine and Wilf's theorem for three periods and a generalization of Sturmian words. Theoret. Comput. Sci. 218 (1999) 83–94. CrossRef
Chekhova, N., Hubert, P. and Messaoudi, A., Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci. J. Théor. Nombres Bordeaux  13 (2001) 371–394. CrossRef
Coven, E.M., Sequences with minimal block growth II. Math. Syst. Theor. 8 (1974) 376–382. CrossRef
Coven, E.M. and Hedlund, G.A., Sequences with minimal block growth. Math. Syst. Theor. 7 (1973) 138–153. CrossRef
Crisp, D., Moran, W., Pollington, A. and Shiue, P., Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux 5 (1993) 123–137. CrossRef
Damanik, D. and Lenz, D., The index of Sturmian sequences. Eur. J. Combin. 23 (2002) 23–29. CrossRef
Damanik, D. and Zamboni, L.Q., Combinatorial properties of Arnoux-Rauzy subshifts and applications to Schrödinger operators. Rev. Math. Phys. 15 (2003) 745–763. CrossRef
de Luca, A., Sturmian words: structure. combinatorics and their arithmetics. Theoret. Comput. Sci. 183 (1997) 45–82. CrossRef
de Luca, A., Glen, A. and Zamboni, L.Q., Rich, Sturmian, and trapezoidal words. Theoret. Comput. Sci. 407 (2008) 569–573. CrossRef
Droubay, X. and Pirillo, G., Palindromes and Sturmian words. Theoret. Comput. Sci. 223 (1999) 73–85. CrossRef
Droubay, X., Justin, J. and Pirillo, G., Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001) 539–553. CrossRef
Durand, F., A characterization of substitutive sequences using return words. Discrete Math. 179 (1998) 89–101. CrossRef
Durand, F., A generalization of Cobham's theorem. Theor. Comput. Syst. 31 (1998) 169–185. CrossRef
Durand, F., Linearly recurrent subshifts have a finite number of non-periodic subshift factors. Ergod. Theor. Dyn. Syst. 19 (1999) 953–993. CrossRef
Fagnot, I., A little more about morphic Sturmian words. RAIRO-Theor. Inf. Appl. 40 (2006) 511–518. CrossRef
Fagnot, I. and Vuillon, L., Generalized balances in Sturmian words. Discrete Appl. Math. 121 (2002) 83–101. CrossRef
Ferenczi, S., Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145–154. CrossRef
Ferenczi, S. and Mauduit, C., Transcendence of numbers with a low complexity expansion. J. Number Theory 67 (1997) 146–161. CrossRef
Ferenczi, S., Mauduit, C. and Nogueira, A., Substitutional dynamical systems: algebraic characterization of eigenvalues. Ann. Sci. École Norm. Sup. 29 (1995) 519–533. CrossRef
Ferenczi, S., Holton, C. and Zamboni, L.Q., Structure of three interval exchange transformations I. An arithmetic study. Ann. Inst. Fourier (Grenoble) 51 (2001) 861–901. CrossRef
Fischler, S., Palindromic prefixes and episturmian words. J. Comb. Th. (A) 113 (2006) 1281–1304. CrossRef
Fischler, S., Palindromic prefixes and diophantine approximation. Monatsh. Math. 151 (2007) 11–37. CrossRef
Fraenkel, A.S., Complementing and exactly covering sequences. J. Comb. Th. (A) 14 (1973) 8–20. CrossRef
A. Glen, On Sturmian and episturmian words, and related topics, Ph.D. Thesis. The University of Adelaide, Australia, April (2006).
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.
Glen, A., Powers in a class of $\mathcal{A}$ -strict standard episturmian words. Theoret. Comput. Sci. 380 (2007) 330–354. CrossRef
Glen, A., A characterization of fine words over a finite alphabet. Theoret. Comput. Sci. 391 (2008) 51–60. CrossRef
Glen, A., Justin, J. and Pirillo, G., Characterizations of finite and infinite episturmian words via lexicographic orderings. Eur. J. Combin. 29 (2008) 45–58. CrossRef
Glen, A., Levé, F. and Richomme, G., Quasiperiodic and Lyndon episturmian words. Theoret. Comput. Sci. 409 (2008) 578–600. CrossRef
Glen, A., Justin, J., Widmer, S. and Zamboni, L.Q., Palindromic richness. Eur. J. Combin. 30 (2009) 510–531. CrossRef
Glen, A., Levé, F. and Richomme, G., Directive words of episturmian words: equivalences and normalization. RAIRO-Theor. Inf. Appl. 43 (2009) 299–319. CrossRef
E. Godelle, Représentation par des transvections des groupes dartin-tits. Group, Geometry and Dynamics 1 (2007) 111–133.
Heinis, A. and Tijdeman, R., Characterisation of asymptotically Sturmian sequences. Publ. Math. Debrecen 56 (2000) 415–430.
Holton, C. and Zamboni, L.Q., Descendants of primitive substitutions. Theor. Comput. Syst. 32 (1999) 133–157. CrossRef
Hubert, P., Suites équilibrés. Theoret. Comput. Sci. 242 (2000) 91–108. CrossRef
Jenkinson, O. and Zamboni, L.Q., Characterisations of balanced words via orderings. Theoret. Comput. Sci 310 (2004) 247–271. CrossRef
Justin, J., On a paper by Castelli, Mignosi, Restivo. RAIRO-Theor. Inf. Appl. 34 (2000) 373–377. CrossRef
Justin, J., Episturmian morphisms and a Galois theorem on continued fractions. RAIRO-Theor. Inf. Appl. 39 (2005) 207–215. CrossRef
Justin, J. and Pirillo, G., Fractional powers in Sturmian words. Theoret. Comput. Sci. 255 (2001) 363–376. CrossRef
Justin, J. and Pirillo, G., Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281–313. CrossRef
Justin, J. and Pirillo, G., On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl. 36 (2002) 385–388. CrossRef
Justin, J. and Pirillo, G., Episturmian words: shifts, morphisms and numeration systems. Internat. J. Found. Comput. Sci. 15 (2004) 329–348. CrossRef
Justin, J. and Vuillon, L., Return words in Sturmian and episturmian words. RAIRO-Theor. Inf. Appl. 34 (2000) 343–356. CrossRef
Komatsu, T. and van der Poorten, A.J., Substitution invariant Beatty sequences. Jpn J. Math. 22 (1996) 349–354.
Krieger, D., On stabilizers of infinite words. Theoret. Comput. Sci. 400 (2008) 169–181. CrossRef
Levé, F. and Richomme, G., Quasiperiodic infinite words: some answers. Bull. Eur. Assoc. Theor. Comput. Sci. 84 (2004) 128–138.
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.
Levé, F. and Richomme, G., Quasiperiodic Sturmian words and morphisms. Theoret. Comput. Sci. 372 (2007) 15–25. CrossRef
M. Lothaire, Combinatorics on Words, Vol. 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, Massachusetts (1983).
M. Lothaire, Algebraic Combinatorics on Words, Vol. 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, UK, (2002).
M. Lothaire, Applied Combinatorics on Words, Vol. 105 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, UK, (2005).
S. Marcus, Quasiperiodic infinite words, Bull. Eur. Assoc. Theor. Comput. Sci. (EATCS) 82 (2004) 170–174.
Mignosi, F. and Pirillo, G., Repetitions in the Fibonacci infinite word. Theor. Inform. Appl. 26 (1992) 199–204. CrossRef
Mignosi, F. and Séébold, P., Morphismes Sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux 5 (1993) 221–233. CrossRef
Mignosi, F. and Zamboni, L.Q., On the number of Arnoux-Rauzy words. Acta Arith. 101 (2002) 121–129. CrossRef
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).
T. Monteil and S. Marcus, Quasiperiodic infinite words: multi-scale case and dynamical properties. Theoret. Comput. Sci., to appear, arXiv:math/0603354v1.
Morse, M. and Hedlund, G.A., Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1–42. CrossRef
Paquin, G. and Vuillon, L., A characterization of balanced episturmian sequences. Electr. J. Combin. 14 (2007) 12.
Pirillo, G., Inequalities characterizing standard Sturmian words. Pure Math. Appl. 14 (2003) 141–144.
Pirillo, G., Inequalities characterizing standard Sturmian and episturmian words. Theoret. Comput. Sci. 341 (2005) 276–292. CrossRef
Pirillo, G., Morse and Hedlund's skew Sturmian words revisited. Ann. Comb. 12 (2008) 115–121. CrossRef
N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, Vol. 1794 of Lect. Notes Math. Springer-Verlag, Berlin (2002).
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.
Rauzy, G., Mots infinis en arithmétique, in Automata On Infinite Words, edited by M. Nivat, D. Perrin. Lect. Notes Comput. Sci. 192 (1985) 165–171.
Richomme, G., Conjugacy and episturmian morphisms. Theoret. Comput. Sci. 302 (2003) 1–34. CrossRef
Richomme, G., Lyndon morphisms. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 761–785.
Richomme, G., 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. CrossRef
Richomme, G., Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. Theoret. Comput. Sci. 380 (2007) 393–400. CrossRef
Richomme, G., On morphisms preserving infinite Lyndon words. Discrete Math. Theor. Comput. Sci. 9 (2007) 89–108.
G. Richomme, private communication (2007).
Risley, R.N. and Zamboni, L.Q., A generalization of Sturmian sequences: Combinatorial structure and transcendence. Acta Arith. 95 (2000) 167–184.
Siegel, A., Pure discrete spectrum dynamical systems and periodic tiling associated with a substitution. Ann. Inst. Fourier (Grenoble) 54 (2004) 341–381. CrossRef
Tan, B. and Wen, Z.-Y., Some properties of the Tribonacci sequence. Eur. J. Combin. 28 (2007) 1703–1719. CrossRef
Tijdeman, R., On complementary triples of Sturmian bisequences. Indag. Math. 7 (1996) 419–424. CrossRef
Tijdeman, R., Intertwinings of Sturmian sequences. Indag. Math. 9 (1998) 113–122. CrossRef
Tijdeman, R., Fraenkel's conjecture for six sequences. Discrete Math. 222 (2000) 223–234. CrossRef
Vandeth, D., Sturmian words and words with a critical exponent. Theoret. Comput. Sci. 242 (2000) 283–300. CrossRef
Veerman, P., Symbolic dynamics and rotation numbers. Physica A 134 (1986) 543–576. CrossRef
Veerman, P., Symbolic dynamics of order-preserving orbits. Physica D 29 (1987) 191–201. CrossRef
Vuillon, L., A characterization of Sturmian words by return words. Eur. J. Combin. 22 (2001) 263–275. CrossRef
Vuillon, L., Balanced words. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 787–805.
Wen, Z.-X. and Zhang, Y., Some remarks on invertible substitutions on three letter alphabet. Chinese Sci. Bull. 44 (1999) 1755–1760. CrossRef
Wozny, N. and Zamboni, L.Q., Frequencies of factors in Arnoux-Rauzy sequences. Acta Arith. 96 (2001) 261–278. CrossRef
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.
Zamboni, L.Q., 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. CrossRef