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.

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 : 10.1051/ita/2011002
Classification : 68R15
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2011002/

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

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

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

[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

[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

[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

[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

[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] Y. Baryshnikov, Complexity of trajectories in rectangular billiards. Commun. Math. Phys. 174 (1995) 43-56. | Zbl

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

[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

[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

[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

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

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

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

[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

[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

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

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

[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

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

[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

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

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

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

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

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

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

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

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

[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

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

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

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

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

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

[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

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

[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

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

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

[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

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

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

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

Cité par Sources :