Abstract.
We address the characterization of finite test-sets for cube-freeness
of morphisms between free monoids, that is, the finite sets T
such
that a morphism f is cube-free if and only if
f (T)
is cube-free. We first prove that such a finite test-set does not exist
for morphisms defined on an alphabet containing at least three letters.
Then we prove that for binary morphisms, a set T of cube-free
words
is a test-set 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.We also prove that, given an alphabet A
containing
at least two letters, the monoid of cube-free endomorphisms on A
is not finitely generated.
Résumé.
Nous nous intéressons à la caractérisation des
ensembles finis de test permettant de tester si un morphisme de
monoïdes
libres est sans cube, i.e., des ensembles finis T tels que un
morphisme
f
est sans cube si et seulement si f( T) est sans cube.
Nous
montrons tout d'abord qu'un tel ensemble n'existe pas pour des
morphismes
définis à partir d'un alphabet d'au moins trois lettres.
Nous montrons ensuite que pour les alphabets binaires, un ensemble
T
de mots sans-cube est un ensemble de test si et seulement si il
contient
douze mots particuliers. En conséquence, un morphisme f
est
sans-cube sur l'alphabet {a,b} si et seulement si f(aabbababbabbaabaababaabb
) est sans cube (la longueur 24 de ce mot est optimale). Une autre
conséquence
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 au plus 7 sont sans cube.
Nous montrons également qu'étant donné un alphabet
A
contenant au moins deux lettres, le monoïde des endomorphismes
sans-cube
sur A n'est pas finiment engendré.
@inproceedings{RW2000,
author = {Richomme, G. and Wlazinski, F.},
title = {About Cube-Free Morphisms},
booktitle = {STACS'2000},
pages = {99-109},
year = {2000},
editor = {Reichel, H. and Tison, S.},
volume = {1770},
series = {Lecture Notes in Computer Science},
}