Abstract FR:

Cette thèse porte sur les monoi͏̈des partiellement commutatifs libres ou monoi͏̈des trace, qui constituent un des principaux modèles sémantiques du parallélisme. Les thèmes abordés sont essentiellement la reconnaissabilité des langages trace et le codage sur les monoi͏̈des trace. Pour ce qui concerne le premier thème, nous donnons une nouvelle preuve de la clôture par produit de la famille des langages trace reconnaissables. Notre approche utilise une décomposition du langage produit induite par un treillis associé au graphe des commutations. Cela fournit un algorithme effectif pour le calcul du produit de deux langages trace. Nous démontrons ensuite que dans un monoi͏̈de finiment engendre quelconque la famille des ensembles apériodiques est contenue (en général strictement) dans la famille des ensembles sans étoile, et nous étendons le théorème de Schitzenberger, établi sur les mots, aux traces: la famille des langages trace apériodiques coi͏̈ncide avec la famille des langages trace sans étoile. Avec l'idée d'étendre la notion de codage aux traces, nous étudions essentiellement le problème de l'existence d'un morphisme injectif entre monoi͏̈des trace. Pour cela nous introduisons la nouvelle notion de morphisme fort, qui impose que deux lettres indépendantes aient pour images des traces indépendantes