Logo image
Overlap-free morphisms and finite test-sets
Article de revue scientifique   Avec comité de lecture

Overlap-free morphisms and finite test-sets

Gwenaël Richomme et Francis Wlazinski
Discrete Applied Mathematics, Vol.143(1-3), p.92-109
30/09/2004

Résumé

Computer Science Discrete Mathematics
We study finite test-sets for overlap-freeness of morphisms from a free monoid A* into another B*. 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. For other values of card(A) and card(B), we show whether or not exist such finite test-sets, and in the former case we characterize all of them. We also do this when considering uniform morphisms for all values of card(A) and card(B).

Indicateurs

1 Consultations de la notice

Détails

Logo image