Balances and abelian complexity of a certain class of infinite ternary words

Turek, Ondřej

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 3, pp. 313-337

Résumé

A word u defined over an alphabet $𝒜$ is c-balanced (c ∈ $\mathbb{N}$) 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 ${\phi }_p$ defined by ${\phi }_p$(L) = L^pS, ${\phi }_p$(S) = M, ${\phi }_p$(M) = L^p-1S where p > 1. We prove that the fixed point of ${\phi }_p$, formally written as ${\phi }_p^{\infty }$(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.

Détail

DOI : 10.1051/ita/2010017

Classification : 68R15
Keywords: balance property, abelian complexity, substitution, ternary word