Abstract FR:

L'apparition du parallélisme dans les calculs et les programmes a entraîné le besoin de modèles formels performants dont les plus utilisés sont les réseaux de Pétri, les langages traces et, plus récemment, les semi-commutation. La question qui vient naturellement à l'esprit quand on étudie une nouvelle opération est : peut-elle être simulée aux moyens d'opérations plus simples ? Nous répondons donc ici à la question : peut-on décomposer les semi-commutations ? Nous démontrons que toute semi-commutation peut être vue comme la composition de semi-commutations élémentaires que nous appelons semi-commutations atomiques. Nous proposons un algorithme effectif de décomposition. Nous pouvons alors donner une nouvelle démonstration d'un théorème permettant de décomposer toute semi-commutations en homomorphismes non effacants, homomorphismes inverses et commutations partielles. Nous établissons une caractérisation des semi-commutations qui préservent la famille des langages multicompteurs : les semi-commutations à compteurs. Elles ont, entre autres, la propriété d'être composables. Elles nous permettent également de résoudre certains problèmes de décidabilité. Nous fournissons quelques résultats quant à la complexité de l'algorithme de décomposition des semi-commutations, certains résultats étant démontrés grâce à l'utilisation des semi-commutations atomiques maximales qui ont une structure proche des semi-commutations à compteurs. Nous proposons enfin un algorithme simple qui permet de décider si un rationnel (dont on connaît l'automate réduit déterministe) est fermé par une semi-commutation donnée