Some non finitely generated monoids of repetition-free endomorphisms
Information Processing Letters 85(2), p61-66, 2003.

Abstract.
We answer a question raised by V. Mitrana in Information Processing Letters 64 about primitive morphisms, that is, morphisms that preserve primitiveness of words. Given an alphabet A with Card(A) >= 2, the monoid of primitive endomorphisms on A and the monoid of primitive uniform endomorphisms on A are not finitely generated.
Moreover we show that it is also the case for the following monoids: the monoid of overlap-free (uniform) endomorphisms on A (when Card(A) >= 3), the monoid of k-power-free (uniform) endomorphisms on A (when Card(A) >= 2 and k >=3).

Résumé.
Nous répondons à une question de V. Mitrana dans Information Processing Letters 64 sur les morphismes primitifs, i.e., les morphismes qui préservent les mots primitifs. Etant donné un alphabet A avec Card(A) >= 2, le monoïde des endomorphismes primitifs sur A et le monoïde des endomorphismes uniformes primitifs sur A ne sont pas finiment engendrés. De plus nous montrons que c'est aussi le cas pour les monoïdes suivants : le monoïde des endomorphismes (uniformes) sans-chevauchement sur  A (quand Card(A) >= 3), le monoïde des endomorphismes (uniformes) sans puissance k (quand  Card(A) >= 2 et k >=3).


Rapport 2002-06, LaRIA, 2002. 

Version postscript compressé de ce rapport (version soumise non corrigée de l'article paru dans IPL)