Abstract FR:

Nous nous intéressons à la vérification de systèmes concurrents tels que les automates communicants et les réseaux de Petri. La vérification de tels systèmes est difficile parce que la présence des composants concurrents augmente de façon importante le nombre des états globaux. Divers techniques ont été proposées pour combattre ce phénomène d'explosion combinatoire. Dans cette thèse, nous nous concentrons sur la technique de dépliage de réseau de Petri. Cette technique tire parti de l'indépendance des actions pour donner une représentation concise des états d'un réseau de Petri. De nombreux travaux ont été réalisés dans ce domaine, mais les aspects d'implémentation ont été souvent négligés. A partir d'une étude expérimentale, nous mettons en avant les parties critiques d'un algorithme de dépliage. Nous proposons de nouvelles stratégies pour diminuer le temps et ccupation-mémoire du calcul. Certaines sont basées sur des techniques de cache et d'autres réduisent le nombre d'appels aux fonctions critiques. Nous introduisons ensuite un nouveau modèle: le produit de réseaux de Petri symétriques. Il nous permet d'effectuer le dépliage de façon modulaire. Nous l'appliquons au produit d'automates. Et les symétries nous permettent d'utiliser des files non bornées. Ces travaux aboutissent à la réalisation d'un outil, l'outil KissPN.