Overlap-free morphisms and finite test-sets. 
avec F. WLAZINSKI
Rapport 2002-05, LaRIA, 2002.

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.