Some results on k-power-free morphisms
avec F. WLAZINSKI
Theoret. Comput. Science, 273:119-142, 2002. 

Abstract.
One way to generate infinite k-power-free words is to iterate a k-power-free morphism, that is a morphism that preserves finite k-power-free words. We first prove that the monoid of k -power-free endomorphisms on an alphabet containing at least three letters is not finitely generated.

Test-sets for k-power-free morphisms (that is, the sets T such that a morphism f is k -power-free if and only if f(T) is k-power-free) give characterizations of these morphisms. In the case of binary morphisms and k = 3, we prove that a set T of cube-free words is a test-set for cube-freeness if and only if it contains twelve particular factors. Consequently, a morphism f on { a,b} is cube-free if and only if f(aabbababbabbaabaababaabb ) is cube-free (length 24 is optimal). Another consequence is an unpublished result of Leconte: A binary morphism is cube-free if and only if the images of all cube-free words of length 7 are cube-free. When k >= 3, we show that no finite test-set exists for morphisms defined on an alphabet containing at least three letters.

In the last part, we show that to generate an infinite cube-free word by iterating a morphism, we do not necessarily need a cube-free morphism. We give a new characterization of some morphisms that generate infinite cube-free words.

Résumé.
Une façon d'obtenir un mot infini sans puissance k consiste à itérer un morphisme sans puissance k, c'est à dire, un morphisme qui préserve les mots sans puissance k. Nous montrons tout d'abord que le monoïde des morphismes sans puissance k n'est pas finiment engendré.Un ensemble de test pour les morphismes sans puissance k est un ensemble T de mots tel que pour tout morphisme f, f est sans puissance k si et seulement si f(T) est sans puissance k : tout ensemble de test fournit une caractérisation des morphismes sans puissance k . Dans le cas des morphismes binaires et pour k = 3, nous montrons qu'un ensemble T de mots sans cube est un ensemble de test pour les morphismes sans cube si et seulement si T contient douze facteurs particuliers. En particulier, un morphisme f défini sur l'alphabet { a,b} est sans cube si et seulement si le mot f( aabbababbabbaabaababaabb) est sans cube (la longueur 24 de ce mot est optimale). Une autre conséquence de la précédente caractérisation d'ensembles de test est un résultat non publié de Leconte : un morphisme binaire est sans cube si et seulement si les images de tous les mots sans cube de longueur 7 sont sans cube. Dans le cas k >= 3, nous montrons qu'il n'existe pas d'ensemble fini de tests pour les morphismes sans puissance k définis sur un alphabet d'au moins trois lettres.

Dans la dernière partie, nous montrons qu'on peut obtenir un mot infini sans cube en itérant un morphisme qui ne préserve pas les mots sans cube. Nous donnons ensuite une nouvelle caractérisation d'une famille de morphismes permettant de générer des mots infinis sans cube

@Article{RW2002,
  author = {Richomme, G. and Wlazinski, F.},
  title = {Some results on $k$-power-free morphisms},
  journal = TCS,
  year = {2002},
  volume = {273},
  pages = {119-142},
}