Décomposition des semi commutations
- Langue : Français
- Discipline : Informatique
- Identifiant : Inconnu
- Type de thèse : Doctorat
- Date de soutenance : 01/01/1993
Résumé en langue originale
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
- Directeur(s) de thèse : Clerbout, Mireille
AUTEUR
- Gonzalez, Dominique