Some results on k-power-free morphisms
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 12 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 greater than or equal to 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. (C) 2002 Elsevier Science B.V. All rights reserved.
morphisms k-power-free words test-sets combinatorics on words