Sturmian jungle (or garden?) on multiliteral alphabets
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 44 (2010) no. 4, p. 443-470

The properties characterizing sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized definitions of sturmian words.

DOI : https://doi.org/10.1051/ita/2011002
Classification:  68R15
Keywords: sturmian words, generalizations of sturmian words, palindromes, rich words
@article{ITA_2010__44_4_443_0,
     author = {Balkov\'a, L'ubom\'\i ra and Pelantov\'a, Edita and Starosta, \v St\v ep\'an},
     title = {Sturmian jungle (or garden?) on multiliteral alphabets},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {4},
     year = {2010},
     pages = {443-470},
     doi = {10.1051/ita/2011002},
     mrnumber = {2775406},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2010__44_4_443_0}
}
Balková, L'ubomíra; Pelantová, Edita; Starosta, Štěpán. Sturmian jungle (or garden?) on multiliteral alphabets. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 44 (2010) no. 4, pp. 443-470. doi : 10.1051/ita/2011002. http://www.numdam.org/item/ITA_2010__44_4_443_0/

[1] B. Adamczewski, Codages de rotations et phénomènes d'autosimilarité. J. Théor. Nombres Bordeaux 14 (2002) 351-386. | Zbl 1113.37003

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

[3] J.P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity. Theoret. Comput. Sci. 292 (2003) 9-31. | Zbl 1064.68074

[4] P. Ambrož, Ch. Frougny, Z. Masáková and E. Pelantová, Palindromic complexity of infinite words associated with simple Parry numbers. Ann. Inst. Fourier 56 (2006) 2131-2160. | Numdam | Zbl 1121.68089

[5] P. Arnoux, C. Mauduit, I. Shiokawa and J.-I. Tamura, Complexity of sequences defined by billiards in the cube. Bull. Soc. Math. France 122 (1994) 1-12. | Numdam | Zbl 0791.58034

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

[7] P. Baláži, Z. Masáková and E. Pelantová, Factor versus palindromic complexity of uniformly recurrent infinite words. Theoret. Comput. Sci. 380 (2007) 266-275. | Zbl 1119.68137

[8] L'. Balková, E. Pelantová and Å. Starosta, Palindromes in infinite ternary words. RAIRO-Theor. Inf. Appl. 43 (2009) 687-702. | Zbl 1191.68476

[9] L'. Balková, E. Pelantová and W. Steiner, Sequences with constant number of return words. Monatsh. Math. 155 (2008) 251-263. | Zbl 1185.68503

[10] L'. Balková, E. Pelantová and O. Turek, Combinatorial and arithmetical properties of infinite words associated with quadratic non-simple Parry numbers. RAIRO-Theor. Inf. Appl. 41 (2007) 307-328. | Zbl 1144.11009

[11] Y. Baryshnikov, Complexity of trajectories in rectangular billiards. Commun. Math. Phys. 174 (1995) 43-56. | Zbl 0839.11006

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

[13] J. Berstel, L. Boasson, O. Carton and I. Fagnot, Infinite words without palindromes. arXiv:0903.2382 (2009), in Proc. CoRR 2009.

[14] J.P. Borel, Complexity and palindromic complexity of billiards words, in Proceedings of WORDS 2005, edited by S. Brlek, C. Reutenauer (2005) 175-183.

[15] S. Brlek, S. Hamel, M. Nivat and C. Reutenauer, On the palindromic complexity of infinite words. Int. J. Found. Comput. Sci. 2 (2004) 293-306. | Zbl 1067.68113

[16] M. Bucci, A. De Luca, A. Glen and L.Q. Zamboni, A connection between palindromic and factor complexity using return words. Adv. Appl. Math. 42 (2009) 60-74. | Zbl 1160.68027

[17] M. Bucci, A. De Luca, A. Glen and L.Q. Zamboni, A new characteristic property of rich words. Theoret. Comput. Sci. 410 (2009) 2860-2863. | Zbl 1173.68048

[18] J. Cassaigne, Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin 4 1 (1997) 67-88. | Zbl 0921.68065

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

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

[21] J. Currie and N. Rampersad, Recurrent words with constant Abelian complexity. Adv. Appl. Math. (2010) DOI: 10.1016/j.aam.2010.05.001

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

[23] X. Droubay, J. Justin and G. Pirillo, Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001) 539-553. | Zbl 0981.68126

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

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

[26] S. Ferenczi, Les transformations de Chacon: combinatoire, structure géométrique, lien avec les systèmes de complexité 2n + 1. Bull. Soc. Math. France 123 (1995) 271-292. | Numdam | Zbl 0855.28008

[27] S. Ferenczi and L. Zamboni, Languages of k-interval exchange transformations. Bull. Lond. Math. Soc. 40 (2008) 705-714. | Zbl 1147.37008

[28] C. Frougny, Z. Masáková and E. Pelantová, Complexity of infinite words associated with beta-expansions. RAIRO-Theor. Inf. Appl. 38 (2004) 162-184. | Numdam | Zbl 1104.11013

[29] A. Glen and J. Justin, Episturmian words: a survey. RAIRO-Theor. Inf. Appl. 43 (2009) 403-442. | Zbl 1182.68155

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

[31] A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schröodinger operators. Commun. Math. Phys. 174 (1995) 149-159. | Zbl 0839.11009

[32] C. Holton and L.Q. Zamboni, Geometric realizations of substitutions. Bull. Soc. Math. France 126 (1998) 149-179. | Numdam | Zbl 0931.11004

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

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

[35] M.S. Keane, Interval exchange transformations. Math. Z. 141 (1975) 25-31. | Zbl 0278.28010

[36] M. Lothaire, Algebraic combinatorics on words. Encyclopedia of Mathematics and its Applications, 90, Cambridge University Press (2002). | Zbl 1001.68093

[37] Z. Masáková, E. Pelantová, Relation between powers of factors and the recurrence function characterizing Sturmian words. Theoret. Comput. Sci. 410 (2009) 3589-3596. | Zbl 1171.68036

[38] M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math. 60 (1938) 815-866. | JFM 64.0798.04

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

[40] G. Rauzy, Échanges d'intervalles et transformations induites. Acta Arith. 34 (1979) 315-328. | Zbl 0414.28018

[41] G. Richomme, Another characterization of Sturmian words (one more). Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 67 (1999) 173-175. | Zbl 0942.11021

[42] G. Richomme, K. Saari and L.Q. Zamboni, Abelian complexity of minimal subshifts. J. London Math. Soc. (2010) DOI: 10.1112/jlms/jdq063 | Zbl pre05848935

[43] G. Richomme, K. Saari and L.Q. Zamboni, Balance and abelian complexity of the Tribonacci word. Adv. Appl. Math. 45 (2010) 212-231. | Zbl 1203.68131

[44] G. Rote, Sequences with subword complexity 2n. J. Number Theory 46 (1993) 196-213. | Zbl 0804.11023

[45] J. Smillie and C. Ulcigrai, Beyond Sturmian sequences: coding linear trajectories in the regular octagon. Proc. London Math. Soc. (2010) DOI: 10.1112/plms/pdq018 | Zbl pre05859681

[46] S. Tabachnikov, Billiards. Panoramas et synthèse, SMF, Numéro 1 (1995). | Zbl 0833.58001

[47] O. Turek, Balances and Abelian complexity of a certain class of infinite ternary words. RAIRO-Theor. Inf. Appl. 44 (2010) 317-341. | Numdam | Zbl pre05822255

[48] O. Turek, Balance properties of the fixed point of the substitution associated to quadratic simple Pisot numbers. RAIRO-Theor. Inf. Appl. 41 (2007) 123-135. | Zbl 1146.68410

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

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

[51] L. Vuillon, On the number of return words in infinite words with complexity 2n + 1. LIAFA Research Report (2000).