A test-set for k-power-free morphisms.
 

Abstract.
A morphism f is k-power-free iff f(w) is k-power-free whenever w is a k-power-free word.
A morphism f is k-power-free up to m iff f(w) is k-power-free whenever w is a k-power-free word of length at most m.
Given an integer k >= 2, we prove that a binary morphism is k-power-free if and only if it is k-power-free up to k^2.
This bound becomes linear for primitive morphisms: a binary primitive morphism is k-power-free if and only if it is k-power-free up to 2k+1.

Résumé.

Un morphisme est dit sans puissance k si et seulement si l'image de tout mot sans puissance k est aussi sans puissance k.
Un morphisme est dit sans puissance k jusqu'à m si et seulement si l'image de tout mot sans puissance k de longueur inférieure ou égale à m est sans puissance k.
Pour tout entier k >= 2, nous montrons qu'un morphisme binaire est sans puissance k si et seulement si il est sans puissance k jusqu'à k^2.
Cette borne devient linéaire pour les morphismes primitifs : un morphisme binaire primitif est sans puissance k si et seulement si il est sans puissance k jusqu'à 2k+1.

@Article{Wla02,
  author =   {Wlazinski, F.},
  title =    {A test set for $k$-power-free binary morphisms},
  journal =      {Theoretical Informatics and Applications},
  year =     {2001},
  volume =   {35},
  number =   {5},
  month =   {Sept./Oct.},
}


Francis Wlazinski