Abstract FR:

Le sujet de cette these est l'etude des problemes de l'etoile et de la puissance finie dans les monoides libres partiellement commutatifs, modeles pour des comportements distribues. Elle presente tout d'abord ces deux problemes. En utilisant les resultats sur les automates a couts, la decidabilite du probleme de la puissance finie pour des ensembles de traces connexes est demontree. En s'appuyant sur ce resultat, il est determine une famille de monoides de commutation dans lesquels les deux problemes sont decidables. Cette famille contient strictement tous les cas de decidabilite connus a ce jour. La decidabilite du probleme de l'etoile est prouvee pour des ensembles finis contenant au plus quatre traces ou au plus deux traces connexes. Il est ensuite montre que l'etoile d'un ensemble est reconnaissable si et seulement si l'ensemble contenant les traces non connexes de cet ensemble et les traces connexes de son etoile possede la propriete de puissance finie. En utilisant ce resultat, il est montre que dans un monoide de commutation, le probleme de l'etoile est decidable si et seulement si le probleme de la puissance finie est decidable. Il est egalement prouve qu'une procedure proposee pour calculer la cloture d'un ensemble de mots fournit un semi-algorithme pour le probleme de l'etoile. Cette procedure donne egalement de nouvelles preuves de resultats connus sur les ensembles reconnaissables