Semi-commutations et reconnaissabilité

URL d'accès : http://ori-nuxeo.univ-lille1.fr/nuxeo/site/esupver...

Auteur(s):  Wacrenier, Pierre-André
Date de soutenance : 1993
Éditeur(s) : Université Lille1 - Sciences et Technologies 

Langue : Français
Directeur(s) de thèse :  Latteux, Michel
Classification : Mathématiques
Discipline : Informatique
Mots-clés : Commutation, Théorie de la

Résumé : 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.



Cité Scientifique BP 30155 59653 VILLENEUVE D'ASCQ CEDEX Tél.:+33 (0)3 20 43 44 10