Abstract.
Given two alphabets A and B, a morphism from A*
to B* is overlap-free if it preserves overlap-free words. A
test-set
T
for
overlap-freeness of morphisms is a set T of words over
A
such that a morphism f is overlap-free if and only if f(T)
is a set of overlap-free words. When Card(A) = Card(B)
= 2, Berstel and Séébold have shown that such a finite
test-set
exists, and, Richomme and
Séébold
have characterized all of them. Here we study finite test-sets for
overlap-freeness
of morphisms for other values of Card(A) and of Card(B). When
Card(B) > 2 and A = {a, b}, there exist finite
test-sets
for overlap-freeness. We characterize them. When Card(B) >=
Card(A)
>= 3, we show that there is no finite test-set for
overlap-freeness
of arbitrary morphisms. However when Card(B) >= Card(A)
>= 2, there exist finite test-sets for overlap-freeness of
uniform
morphisms. We characterize them.
Résumé.
Étant donné deux alphabets A et B,
un morphisme de A* vers B* est sans chevauchement s'il
préserve
les mots sans chevauchement. Un ensemble de test T pour les
morphismes
sans chevauchement est un ensemble T de mots sur A tel
qu'un
morphisme f est sans chevauchement si et seulement si f(T)
est un ensemble de mots sans chevauchement. Quand Card(A) = Card(B)
= 2. Berstel et Séébold ont montré qu'un tel
ensemble
fini de test existe, et Richomme et
Séébold
les ont caractérisés. Dans ce papier, nous
étudions
les ensembles finis pour morphismes sans chevauchement pour d'autres
valeurs
de Card(A) et de Card(B). Quand Card(B) >
2
et A = {a, b}, il existe des ensembles finis de tests. Nous les
caractérisons. Quand Card(B) >= Card(A)
>= 3,
nous montrons qu'il n'existe pas d'ensemble fini de test. Cependant
quand
Card(B) >= Card(A) >= 2, il existe des
ensembles finis
de test pour les morphismes uniformes sans chevauchement. Nous les
caractérisons
aussi.