Résumé: Cette thèse porte sur les monoïdes partiellement commutatifs libres ou monoï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 monoï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 monoïde finement 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 coï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 monoï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.

Paris:
Langue: Français
Collation: 118 p. ill. ;30 cm.
Diplôme: Doctorat
Etablissement de soutenance: Paris, Université Pierre et Marie Curie. Institut Blaise Pascal
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:
Parallélisme (Informatique)
Morphismes (mathématiques)
Monoïdes

Note: Bibliogr. p.111-118