Résumé: Le problème du mot des monoïdes admettant une présentation a un seul relateur semble décidable. Cependant, aucun algorithme n'a encore été trouve pour le résoudre. Nous présentons le problème, les approches utilisées dans la littérature et celles envisageables. Nous dégageons ensuite des propriétés générales sur certaines factorisations de mots, propriétés qui ont leur intérêt propre dans la combinatoire des mots. Enfin, nous appliquons ces dernières a notre problème dans le cas ou l'un des deux mots constituant le relateur ne se chevauche pas avec lui-même. Pour ce cas, qui, nous le verrons, concerne une très large classe de monoïdes, la meilleure contribution apportée jusqu'ici autorise a décider le problème si le mot qui ne se chevauche pas avec lui-même apparait en facteur dans le second mot. Nous étendons ce résultat en supprimant la contrainte pour le premier mot d'apparaitre dans le second sous réserve que ce premier mot soit d'une longueur au moins égale au carre de la longueur du second mot.

Paris:
Langue: Français
Collation: 99 p. ill. ;30 cm.
Diplôme: Doctorat
Etablissement de soutenance: Paris, Université de Paris 7
Spécialité: Informatique
Index décimal 621 .Physique appliquée (électrotechnique, génie civil, génie mécanique, ingénierie appliquée, principes physiques en ingénierie)
Thème Informatique

Mots clés:
Monoïdes

Note: Bibliogr. pp.97-99