Abelian Complexity of Minimal subshifts

Abstract : In this paper we undertake the general study of the Abelian complexity of an infinite word on a finite alphabet. We investigate both similarities and differences between the Abelian complexity and the usual subword complexity. While the Thue-Morse minimal subshift is neither characterized by its Abelian complexity nor by its subword complexity alone, we show that the subshift is completely characterized by the two complexity functions together. We give an affirmative answer to an old question of Rauzy by exhibiting a class of words whose Abelian complexity is everywhere equal to 3. We also investigate links between Abelian complexity and the existence of Abelian powers. Using van der Waerden's theorem, we show that any minimal subshift having bounded Abelian complexity contains Abelian k-powers for every positive integer k. In the case of Sturmian words, we prove something stronger: for every Sturmian word ω and positive integer k, each sufficiently long factor of ω begins with an Abelian k-power.
Type de document :
Article dans une revue
Journal of the London Mathematical Society, London Mathematical Society, 2011, 83 (1), pp.79-95. 〈10.1112/jlms/jdq063〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00598086
Contributeur : Gwenaël Richomme <>
Soumis le : vendredi 3 juin 2011 - 23:20:30
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Lien texte intégral

Identifiants

Citation

Gwenaël Richomme, Kalle Saari, Luca Q. Zamboni. Abelian Complexity of Minimal subshifts. Journal of the London Mathematical Society, London Mathematical Society, 2011, 83 (1), pp.79-95. 〈10.1112/jlms/jdq063〉. 〈lirmm-00598086〉

Partager

Métriques

Consultations de la notice

236