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.
@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},
volume = {44},
year = {2010},
pages = {443-470},
doi = {10.1051/ita/2011002},
mrnumber = {2775406},
language = {en},
url = {http://dml.mathdoc.fr/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, Tome 44 (2010) pp. 443-470. doi : 10.1051/ita/2011002. http://gdmltest.u-ga.fr/item/ITA_2010__44_4_443_0/
[1] , Codages de rotations et phénomènes d'autosimilarité. J. Théor. Nombres Bordeaux 14 (2002) 351-386. | Zbl 1113.37003
[2] , Balances for fixed points of primitive substitutions. Theoret. Comput. Sci. 307 (2003) 47-75. | Zbl 1059.68083
[3] , , and , Palindrome complexity. Theoret. Comput. Sci. 292 (2003) 9-31. | Zbl 1064.68074
[4] , , and , Palindromic complexity of infinite words associated with simple Parry numbers. Ann. Inst. Fourier 56 (2006) 2131-2160. | Numdam | Zbl 1121.68089
[5] , , and , Complexity of sequences defined by billiards in the cube. Bull. Soc. Math. France 122 (1994) 1-12. | Numdam | Zbl 0791.58034
[6] and , Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France 119 (1991) 199-215. | Numdam | Zbl 0789.28011
[7] , and , 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] , Complexity of trajectories in rectangular billiards. Commun. Math. Phys. 174 (1995) 43-56. | Zbl 0839.11006
[12] , Recent results on extensions of Sturmian words. Int. J. Algebra Comput. 12 (2002) 371-385. | Zbl 1007.68141
[13] , , and , Infinite words without palindromes. arXiv:0903.2382 (2009), in Proc. CoRR 2009.
[14] , Complexity and palindromic complexity of billiards words, in Proceedings of WORDS 2005, edited by S. Brlek, C. Reutenauer (2005) 175-183.
[15] , , and , On the palindromic complexity of infinite words. Int. J. Found. Comput. Sci. 2 (2004) 293-306. | Zbl 1067.68113
[16] , , and , A connection between palindromic and factor complexity using return words. Adv. Appl. Math. 42 (2009) 60-74. | Zbl 1160.68027
[17] , , and , A new characteristic property of rich words. Theoret. Comput. Sci. 410 (2009) 2860-2863. | Zbl 1173.68048
[18] , Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin 4 1 (1997) 67-88. | Zbl 0921.68065
[19] , and , Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier 50 (2000) 1265-1276. | Zbl 1004.37008
[20] and , Sequences with minimal block growth. Math. Syst. Theor. 7 (1973) 138-153. | Zbl 0256.54028
[21] and , Recurrent words with constant Abelian complexity. Adv. Appl. Math. (2010) DOI: 10.1016/j.aam.2010.05.001
[22] and , Palindromes and Sturmian words. Theoret. Comput. Sci. 223 (1999) 73-85. | Zbl 0930.68116
[23] , and , Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001) 539-553. | Zbl 0981.68126
[24] , A characterization of substitutive sequences using return words. Discrete Math. 179 (1998) 89-101. | Zbl 0895.68087
[25] and , Generalized balances in Sturmian words. Discrete Appl. Math. 121 (2002) 83-101. | Zbl 1002.68117
[26] , 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] and , Languages of k-interval exchange transformations. Bull. Lond. Math. Soc. 40 (2008) 705-714. | Zbl 1147.37008
[28] , and , Complexity of infinite words associated with beta-expansions. RAIRO-Theor. Inf. Appl. 38 (2004) 162-184. | Numdam | Zbl 1104.11013
[29] and , Episturmian words: a survey. RAIRO-Theor. Inf. Appl. 43 (2009) 403-442. | Zbl 1182.68155
[30] , , and , Palindromic richness. Eur. J. Comb. 30 (2009) 510-531. | Zbl 1169.68040
[31] , and , Singular continuous spectrum for palindromic Schröodinger operators. Commun. Math. Phys. 174 (1995) 149-159. | Zbl 0839.11009
[32] and , Geometric realizations of substitutions. Bull. Soc. Math. France 126 (1998) 149-179. | Numdam | Zbl 0931.11004
[33] and , Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281-313. | Zbl 1002.68116
[34] and , Return words in Sturmian and episturmian words. RAIRO-Theor. Inf. Appl. 34 (2000) 343-356. | Numdam | Zbl 0987.68055
[35] , Interval exchange transformations. Math. Z. 141 (1975) 25-31. | Zbl 0278.28010
[36] , Algebraic combinatorics on words. Encyclopedia of Mathematics and its Applications, 90, Cambridge University Press (2002). | Zbl 1001.68093
[37] , , Relation between powers of factors and the recurrence function characterizing Sturmian words. Theoret. Comput. Sci. 410 (2009) 3589-3596. | Zbl 1171.68036
[38] and , Symbolic dynamics. Amer. J. Math. 60 (1938) 815-866. | JFM 64.0798.04
[39] and , Symbolic dynamics II - Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM 66.0188.03
[40] , Échanges d'intervalles et transformations induites. Acta Arith. 34 (1979) 315-328. | Zbl 0414.28018
[41] , Another characterization of Sturmian words (one more). Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 67 (1999) 173-175. | Zbl 0942.11021
[42] , and , Abelian complexity of minimal subshifts. J. London Math. Soc. (2010) DOI: 10.1112/jlms/jdq063 | Zbl pre05848935
[43] , and , Balance and abelian complexity of the Tribonacci word. Adv. Appl. Math. 45 (2010) 212-231. | Zbl 1203.68131
[44] , Sequences with subword complexity 2n. J. Number Theory 46 (1993) 196-213. | Zbl 0804.11023
[45] and , Beyond Sturmian sequences: coding linear trajectories in the regular octagon. Proc. London Math. Soc. (2010) DOI: 10.1112/plms/pdq018 | Zbl pre05859681
[46] , Billiards. Panoramas et synthèse, SMF, Numéro 1 (1995). | Zbl 0833.58001
[47] , Balances and Abelian complexity of a certain class of infinite ternary words. RAIRO-Theor. Inf. Appl. 44 (2010) 317-341. | Numdam | Zbl pre05822255
[48] , 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] , A characterization of Sturmian words by return words. Eur. J. Comb. 22 (2001) 263-275. | Zbl 0968.68124
[50] , Balanced words. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 787-805. | Zbl 1070.68129
[51] , On the number of return words in infinite words with complexity 2n + 1. LIAFA Research Report (2000).