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},
}