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.