Balances and abelian complexity of a certain class of infinite ternary words
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 3, pp. 313-337.

A word u defined over an alphabet 𝒜 is c-balanced (c ) if for all pairs of factors v, w of u of the same length and for all letters a 𝒜, the difference between the number of letters a in v and w is less or equal to c. In this paper we consider a ternary alphabet 𝒜 = {L, S, M} and a class of substitutions φ p defined by φ p (L) = LpS, φ p (S) = M, φ p (M) = Lp-1S where p > 1. We prove that the fixed point of φ p , formally written as φ p (L), is 3-balanced and that its abelian complexity is bounded above by the value 7, regardless of the value of p. We also show that both these bounds are optimal, i.e. they cannot be improved.

DOI : https://doi.org/10.1051/ita/2010017
Classification : 68R15
Mots clés : balance property, abelian complexity, substitution, ternary word
@article{ITA_2010__44_3_313_0,
     author = {Turek, Ond\v{r}ej},
     title = {Balances and abelian complexity of a certain class of infinite ternary words},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {313--337},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {3},
     year = {2010},
     doi = {10.1051/ita/2010017},
     mrnumber = {2761522},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2010017/}
}
TY  - JOUR
AU  - Turek, Ondřej
TI  - Balances and abelian complexity of a certain class of infinite ternary words
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2010
DA  - 2010///
SP  - 313
EP  - 337
VL  - 44
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2010017/
UR  - https://www.ams.org/mathscinet-getitem?mr=2761522
UR  - https://doi.org/10.1051/ita/2010017
DO  - 10.1051/ita/2010017
LA  - en
ID  - ITA_2010__44_3_313_0
ER  - 
Turek, Ondřej. Balances and abelian complexity of a certain class of infinite ternary words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 3, pp. 313-337. doi : 10.1051/ita/2010017. http://www.numdam.org/articles/10.1051/ita/2010017/

[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] Ľ. Balková, E. Pelantová and Š. Starosta, Sturmian Jungle (or Garden?) on Multiliteral Alphabets. RAIRO: Theoret. Informatics Appl (to appear).

[4] Ľ. Balková, E. Pelantová and O. Turek, Combinatorial and Arithmetical Properties of Infinite Words Associated with Quadratic Non-simple Parry Numbers. RAIRO: Theoret. Informatics Appl. 41 3 (2007) 307-328. | Zbl 1144.11009

[5] V. Berthé and R. Tijdeman, Balance properties of multi-dimensional words. Theoret. Comput. Sci. 273 (2002) 197-224. | Zbl 0997.68091

[6] J. Cassaigne, Recurrence in infinite words, in Proc. STACS, LNCS Dresden (Allemagne) 2010, Springer (2001) 1-11. | Zbl 0976.68524

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

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

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

[10] S. Fabre, Substitutions et β-systèmes de numération. Theoret. Comput. Sci. 137 (1995) 219-236. | Zbl 0872.11017

[11] C. Frougny, J.P. Gazeau and J. Krejcar, Additive and multiplicative properties of point-sets based on beta-integers. Theor. Comp. Sci. 303 (2003) 491-516. | Zbl 1036.11034

[12] K. Klouda and E. Pelantová, Factor complexity of infinite words associated with non-simple Parry numbers. Integers - Electronic Journal of Combinatorial Number Theory (2009) 281-310. | Zbl 1193.68201

[13] M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002).

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

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

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

[17] G. Richomme, K. Saari, L. Q. Zamboni, Abelian Complexity in Minimal Subshifts. J. London Math. Soc. (to appear).

[18] W. Thurston, Groups, tilings and finite state automata. AMS Colloquium Lecture Notes (1989).

[19] O. Turek, Balance properties of the fixed point of the substitution associated to quadratic simple Pisot numbers. RAIRO: Theoret. Informatics Appl. 41 2 (2007) 123-135. | Zbl 1146.68410

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

Cité par Sources :