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)