Contexte : Le problème de la synthèse d'un réseau de Petri est de
décider constructivement de l'existence d'un réseau dont le graphe des
marquages est isomorphe à un système de transitions donné. Le problème de
synthèse peut également être défini pour des langages : il s'agit alors de
décider de l'existence d'un réseau dont le langage est donné sous la forme
d'une expression régulière, et dans l'affirmative de le calculer. Ces problèmes
ont des solutions algorithmiques efficaces qui permettent de générer des
protocoles de communications répartis à partir de spécifications de services,
ou encore de générer des contrôleurs répartis pour des systèmes à événements
discrets.
L'application de ces techniques à des problèmes de vraie grandeur requiert leur extension à des formalismes d'entrée plus expressifs : langages algébriques, diagrammes de séquences (MSC), automates étendus (comportant des commandes gardées sur des variables entières). Dans certains de ces formalismes, des algorithmes de synthèse sont connus : ils reposent sur des calculs sur les régions dans les systèmes de transitions ou les langages, et la manipulation d'ensembles semi-linéaires de vecteurs d'entiers.
Objectif de travail :
Le travail de stage se fera dans deux directions :
Débouchés :
Ce stage de DEA est destiné à être poursuivi par un doctorat (avec bourse
de l'INRIA) sur les techniques de synthèse de réseaux de Petri et leurs
applications aux problèmes de génération de programmes répartis : protocoles de
communication, contrôleurs de systèmes à événements discrets, etc.