Les réseaux de Petri : définitions, propriétés et analyse

Résumé du document

- Avantages
. Notion d'état et de changement d'état,
. Possibilité de représenter un nombre infini d'état (langage des parenthèses),
. Possibilité de preuve,
. Communauté active : outils, algorithmes de preuves, nouvelles classes de RdP, ...

- Inconvénients
. Non hiérarchique,
. Explosion des spécifications,
. Inutilisable tel quel pour les interfaces.

(...)

- Soient :
. M0, le marquage initial d'un réseau,
. *M0, l'ensemble des marquages accessibles à partir de M0,
. Pi une des places du réseau,
. Ti l'une de ses transitions.

(...)

- On se ramène à un automate à état fini :
. Chaque état correspond à un marquage possible,
. Lorsqu'une place n'est pas bornée, on utilise le symbole w pour noter son marquage,
- On fait des preuves sur cet automate là.

(...)

Extraits

[...] 05/11/19 < number > Exemple OPN 05/11/19 < number > Pattern Séquence : Choix : 05/11/19 < number > Pattern Boucle : 05/11/19 < number > Pattern Mise en parallèle de deux processus : Synchronisation de deux processus : 05/11/19 < number > Bilan Avantages Notion d'état et de changement d'état Possibilité de représenter un nombre infini d'état (langage des parenthèses) Possibilité de preuve Communauté active : outils, algorithmes de preuves, nouvelles classes de RdP 05/11/19 < number > Bilan Inconvénients Non hiérarchique Explosion des spécifications Inutilisable tel quel pour les interfaces 05/11/19 < number > Plan Définitions : Les réseaux de Petri Les réseaux de Petri à objets Patterns Propriétés Analyse 05/11/19 < number > Définitions Soient : M0, le marquage initial d'un réseau, l'ensemble des marquages accessibles à partir de M0 Pi une des places du réseau, Ti l'une de ses transitions. 05/11/19 < number > RdP borné Pi est bornée pour M0 si  k  N tq  M(Pi) k. Un réseau de Petri est dit borné pour M0 si toutes ses places sont bornées pour M0. Si un réseau de Petri est non-borné pour M0, il est non borné  M0' M0 05/11/19 < number > RdP sauf Un réseau de Petri est dit sauf (ou binaire) pour M0 si chacune de ses places contient au plus un jeton. [...]

[...] Un réseau de Petri est vivant pour M0 si toutes ses transitions sont vivantes pour M0. 05/11/19 < number > Blocage Un blocage (ou état-puits) est un marquage tel qu'aucune transition n'est plus valide. Un réseau de Petri est dit sans blocage pour M0 si aucun marquage accessible Mi  *M0 n'est un blocage. 05/11/19 < number > Etat d'accueil Un réseau de Petri a un état d'accueil Ma pour M0 si  Mi   Si tq Mi [Si > Ma . Un réseau de Petri est réinitialisable pour M0 si M0 est état d'accueil pour ce réseau et ce marquage initial. [...]

[...] Une transition Tj est neutre ssi l'ensemble de ses places d'entrée est aussi l'ensemble de ses places de sortie. On peut supprimer une transition neutre et ses arcs s'il existe une transition Tk (avec Tj Tk) telle que Post(Pi,Tk) Pré(Pi,Tj) pour toute place d'entrée Pi de Tj. Propriétés conservées : borné, vivant, quasi vivant, sans blocage, conservatif et état d'accueil. Règle 4 : transitions identiques. Deux transitions sont identiques si elles ont les mêmes places d'entrée et les mêmes places de sortie. On peut alors supprimer l'une d'elles. [...]

[...] La réduction consiste à : Supprimer la transition Tj, A tout couple de places (Pi on associe une place Pi + Pk. Les transitions d'entrée de Pi + Pk sont les transitions d'entrée de Pi et de Pk à l'exception de Tj. Les transitions de sortie de Pi + Pk sont les transitions de sortie de Pi et de Pk à l'exception de Tj. 05/11/19 < number > Exemple 05/11/19 < number > Algèbre linéaire C'est la technique utilisée dans Petshop, C'est la technique d'analyse la plus facile à automatiser Elle s'appuie sur les bases mathématiques des réseaux de Petri 05/11/19 < number > Définitions Tout RdP est Q = : P = PN} est un ensemble fini et non vide de places, T = TM} est un ensemble fini et non vide de transitions, P ∩ T = Pré : P * T est l'application d'incidence avant, Post : P * T est l'application d'incidence arrière, 05/11/19 < number > Exemple VoAnalyse2 05/11/19 < number > Définitions Matrice d'incidence W = Post – Pré Equation fondamentale : S : seq de franchissement, S : son vecteur caractéristique (la composante j de S correspond au nombre de franchissement de la transition Tj dans S). [...]

[...] 05/11/19 < number > Réduction Technique permettant de simplifier un réseau 4 règles pour réduire les réseaux en conservant les propriétés de vivance Algorithme de réduction préservant les invariants. 05/11/19 < number > Préservation des propriétés vivant et borné Règle 1 : Une place Pi peut être substituée si : Ses transitions de sorties n'ont pas d'autres transition d'entrée, Il n'y a pas de transition qui soit à la fois transition d'entrée et transition de sortie de Pi, Pi a au moins une transition de sortie qui ne soit pas transition puit. [...]