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.
Mots-clés : 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{S}t\v{e}p\'an},
title = {Sturmian jungle (or garden?) on multiliteral alphabets},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {443--470},
publisher = {EDP-Sciences},
volume = {44},
number = {4},
year = {2010},
doi = {10.1051/ita/2011002},
mrnumber = {2775406},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2011002/}
}
TY - JOUR AU - Balková, L'ubomíra AU - Pelantová, Edita AU - Starosta, Štěpán TI - Sturmian jungle (or garden?) on multiliteral alphabets JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2010 SP - 443 EP - 470 VL - 44 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2011002/ DO - 10.1051/ita/2011002 LA - en ID - ITA_2010__44_4_443_0 ER -
%0 Journal Article %A Balková, L'ubomíra %A Pelantová, Edita %A Starosta, Štěpán %T Sturmian jungle (or garden?) on multiliteral alphabets %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2010 %P 443-470 %V 44 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2011002/ %R 10.1051/ita/2011002 %G en %F 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) no. 4, pp. 443-470. doi : 10.1051/ita/2011002. http://www.numdam.org/articles/10.1051/ita/2011002/
[1] , Codages de rotations et phénomènes d'autosimilarité. J. Théor. Nombres Bordeaux 14 (2002) 351-386. | Zbl
[2] , Balances for fixed points of primitive substitutions. Theoret. Comput. Sci. 307 (2003) 47-75. | Zbl
[3] , , and , Palindrome complexity. Theoret. Comput. Sci. 292 (2003) 9-31. | Zbl
[4] , , and , Palindromic complexity of infinite words associated with simple Parry numbers. Ann. Inst. Fourier 56 (2006) 2131-2160. | Numdam | Zbl
[5] , , and , Complexity of sequences defined by billiards in the cube. Bull. Soc. Math. France 122 (1994) 1-12. | Numdam | Zbl
[6] and , Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France 119 (1991) 199-215. | Numdam | Zbl
[7] , and , Factor versus palindromic complexity of uniformly recurrent infinite words. Theoret. Comput. Sci. 380 (2007) 266-275. | Zbl
[8] L'. Balková, E. Pelantová and Å. Starosta, Palindromes in infinite ternary words. RAIRO-Theor. Inf. Appl. 43 (2009) 687-702. | Numdam | Zbl
[9] L'. Balková, E. Pelantová and W. Steiner, Sequences with constant number of return words. Monatsh. Math. 155 (2008) 251-263. | Zbl
[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
[11] , Complexity of trajectories in rectangular billiards. Commun. Math. Phys. 174 (1995) 43-56. | Zbl
[12] , Recent results on extensions of Sturmian words. Int. J. Algebra Comput. 12 (2002) 371-385. | Zbl
[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
[16] , , and , A connection between palindromic and factor complexity using return words. Adv. Appl. Math. 42 (2009) 60-74. | Zbl
[17] , , and , A new characteristic property of rich words. Theoret. Comput. Sci. 410 (2009) 2860-2863. | Zbl
[18] , Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin 4 1 (1997) 67-88. | Zbl
[19] , and , Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier 50 (2000) 1265-1276. | Zbl
[20] and , Sequences with minimal block growth. Math. Syst. Theor. 7 (1973) 138-153. | Zbl
[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
[23] , and , Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001) 539-553. | Zbl
[24] , A characterization of substitutive sequences using return words. Discrete Math. 179 (1998) 89-101. | Zbl
[25] and , Generalized balances in Sturmian words. Discrete Appl. Math. 121 (2002) 83-101. | Zbl
[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
[27] and , Languages of k-interval exchange transformations. Bull. Lond. Math. Soc. 40 (2008) 705-714. | Zbl
[28] , and , Complexity of infinite words associated with beta-expansions. RAIRO-Theor. Inf. Appl. 38 (2004) 162-184. | Numdam | Zbl
[29] and , Episturmian words: a survey. RAIRO-Theor. Inf. Appl. 43 (2009) 403-442. | Zbl
[30] , , and , Palindromic richness. Eur. J. Comb. 30 (2009) 510-531. | Zbl
[31] , and , Singular continuous spectrum for palindromic Schröodinger operators. Commun. Math. Phys. 174 (1995) 149-159. | Zbl
[32] and , Geometric realizations of substitutions. Bull. Soc. Math. France 126 (1998) 149-179. | Numdam | Zbl
[33] and , Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281-313. | Zbl
[34] and , Return words in Sturmian and episturmian words. RAIRO-Theor. Inf. Appl. 34 (2000) 343-356. | Numdam | Zbl
[35] , Interval exchange transformations. Math. Z. 141 (1975) 25-31. | Zbl
[36] , Algebraic combinatorics on words. Encyclopedia of Mathematics and its Applications, 90, Cambridge University Press (2002). | Zbl
[37] , , Relation between powers of factors and the recurrence function characterizing Sturmian words. Theoret. Comput. Sci. 410 (2009) 3589-3596. | Zbl
[38] and , Symbolic dynamics. Amer. J. Math. 60 (1938) 815-866. | JFM
[39] and , Symbolic dynamics II - Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM
[40] , Échanges d'intervalles et transformations induites. Acta Arith. 34 (1979) 315-328. | Zbl
[41] , Another characterization of Sturmian words (one more). Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 67 (1999) 173-175. | Zbl
[42] , and , Abelian complexity of minimal subshifts. J. London Math. Soc. (2010) DOI: 10.1112/jlms/jdq063
[43] , and , Balance and abelian complexity of the Tribonacci word. Adv. Appl. Math. 45 (2010) 212-231. | Zbl
[44] , Sequences with subword complexity 2n. J. Number Theory 46 (1993) 196-213. | Zbl
[45] and , Beyond Sturmian sequences: coding linear trajectories in the regular octagon. Proc. London Math. Soc. (2010) DOI: 10.1112/plms/pdq018
[46] , Billiards. Panoramas et synthèse, SMF, Numéro 1 (1995). | Zbl
[47] , Balances and Abelian complexity of a certain class of infinite ternary words. RAIRO-Theor. Inf. Appl. 44 (2010) 317-341. | Numdam
[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
[49] , A characterization of Sturmian words by return words. Eur. J. Comb. 22 (2001) 263-275. | Zbl
[50] , Balanced words. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 787-805. | Zbl
[51] , On the number of return words in infinite words with complexity 2n + 1. LIAFA Research Report (2000).
Cité par Sources :
