Algorithmes de factorisation de monoïdes libres

Abstract

En mathématiques, plus précisément en arithmétique, il existe un théorème affirmant que tout nombre entier peut se décomposer en un produit de puissances de nombres premiers. En combinatoire des mots, le rôle des générateurs de monoïde est joué par les factorisations complètes. Dans ce mémoire, deux familles de mots seront présentées et étudiées : les familles des mots de Lyndon et Nyldon. Il sera, entre autres, montré que ces deux familles munies d'un ordre bien précis forment des factorisations complètes de monoïdes. Après cela, elles seront reliées à deux autres ensembles de mots : les ensembles de Hall et de Lazard. Enfin, durant tout ce travail accompli, plusieurs algorithmes auront été présentés directement ou indirectement. Dès lors, la fin de ce mémoire contiendra une brève étude des différents algorithmes de factorisation et d'autres algorithmes en lien avec la thématique des mots de Nyldon.