On abelian saturated infinite words

Sergey Avgustinovich (1) , Julien Cassaigne (2) , Juhani Karhumaki (3) , Svetlana Puzynina (4) , Aleksi Saarela (5)

1 Sobolev Institute of Mathematics
2 I2M - Institut de Mathématiques de Marseille
3 Department of Mathematics and Statistics, University of Turku
4 Department of Mathematics
5 Turku Centre for Computer Science

Let f : Z + → R be an increasing function. We say that an infinite word w is abelian f (n)-saturated if each factor of length n contains Θ(f (n)) abelian nonequivalent factors. We show that binary infinite words cannot be abelian n 2saturated, but, for any ε > 0, they can be abelian n 2−ε-saturated. There is also a sequence of finite words (w n), with |w n | = n, such that each w n contains at least Cn 2 abelian nonequivalent factors for some constant C > 0. We also consider saturated words and their connection to palindromic richness in the case of equality and k-abelian equivalence.

Domaines: Mathématique discrète [cs.DM]

Sergey Avgustinovich, Julien Cassaigne, Juhani Karhumaki, Svetlana Puzynina, Aleksi Saarela. On abelian saturated infinite words. Theoretical Computer Science, 2019, 792, pp.154-160. ⟨10.1016/j.tcs.2018.05.013⟩. ⟨hal-02375068⟩