Semi-commutations et reconnaissabilité
- Langue : Français
- Discipline : Informatique
- Identifiant : Inconnu
- Type de thèse : Doctorat
- Date de soutenance : 01/01/1993
Résumé en langue originale
Les commutations partielles ont ete utilisees en 1977 par A. Mazurkiewicz pour etudier le comportement de processus paralleles. La notion de semi-commutations generalise celle de commutation partielle ; les semi-commutations permettent de modeliser les programmes a memoire partagee de type producteur/consommateur. Dans une premiere partie nous etudions la composition de deux fonctions de semi-commutation: nous caracterisons les couples de fonctions de semi-commutation dont la composition est une fonction de semi-commutation. Grace a cette caracterisation nous obtenons, en particulier, une caracterisation decidable des semi-commutations confluentes. La seconde partie de ce memoire est consacree aux morphismes pour semi-commutations; ceux-ci permettent de specifier le parallelisme a differents niveaux d'abstraction. Nous etudions les morphismes pour semi-commutations qui preservent la reconnaissabilite et caracterisons les morphismes des monoides de semi-traces qui peuvent etre simules par des transductions rationnelles.
- Directeur(s) de thèse : Latteux, Michel
AUTEUR
- Wacrenier, Pierre-André