Abstract FR:

Les automates asynchrones constituent un modèle qui décrit explicitement le parallélisme des exécutions dans un système distribué à mémoires partagées. Au contraire, les id-automates décrivent l'ensemble des exécutions séquentielles du comportement d'un tel système. Nous avons élaboré une technique de dépliage inédite qui construit à partir d'un id-automate à un automate asynchrone sémantiquement équivalent à A de taille polynomiale à A. Cette construction améliore les complexités des constructions existantes. Les automates communicants (CFM) modélisent des systèmes distribués à passages de messages. Les protocoles de communication employés dans de tels systèmes peuvent être spécifiés au moyen de diagrammes de communication (MSCS). Nous caractérisons les ensembles de MSCS qui peuvent être implémentés en un CFM sans blocage et avec arrêt définitif. Enfin, nous explorons le formalisme des netcharts. Nous montrons entre autres que les modèles des netcharts et des CFMS sont équivalents.