 Certains systèmes logiques ou de commande de systèmes

séquentiels sont souvent complexes et leurs conception pose

des problèmes délicats. Il est donc nécessaire de disposer
d’outils puissants qui permettent de représenter d’une façon
réaliste l’évolution du système de façon a en faciliter la
conception.

 En pratique, la représentation par Réseaux de pétri (RdP) s’est

avérée être un bon compromis entre la souplesse d’emploi et
la puissance de la représentation.

 Les RdP permettent de décrire d’une façon relativement

simple l’évolution d’un processus ou la commande d’un
système séquentiel. Leur usage s’est répandu dans de
nombreux domaines tels que les automatismes, les systèmes
temps réels ou les protocoles de communication.
Définition d'un réseau de Pétri (RdP)
Un réseau de Pétri est un moyen de:
 modélisation du comportement des systèmes
dynamiques à événements discrets.
 description des relations existantes entre des
conditions et des évènements.
 1.1 Places, transitions et arcs

 Un RdP est composé de places, transitions et arcs :

 Une place est représentée par un cercle

 Une transition par un trait

 Un arc relie soit une place à une transition

 soit une transition à une place.

 Chaque place contient un nombre entier positif ou nul de marques ou jetons.
Le marquage M définit l'état du système décrit par le réseau à un instant
donné. C'est un vecteur colonne de dimension le nombre de places dans le
réseau. Le iéme élément du vecteur correspond au nombre de jetons
contenus dans la place Pi .

 Exemple 1
 Une transition est franchissable lorsque toutes les places qui lui sont en
amont (ou toutes les places d'entrée de la transition) contiennent au moins
un jeton.

 Le franchissement consiste à retirer un jeton de chacune des places d'entrée

et à rajouter un jeton à chacune des places de sortie de la même transition.
 Une transition sans place d'entrée est toujours franchissable : c'est une
transition source.
 Le franchissement d'une transition source consiste à rajouter un jeton à
chacune de ces places de sortie.

 Une transition sans place de sortie est une transition puits.

 Le franchissement d'une transition puits consiste à retirer un jeton de
chacune de ses places d'entrée.
Une séquence de franchissement S est une suite de transitions Ti Tj…Tk qui
peuvent être franchies successivement à partir d'un marquage donné. Une seule
transition peut être franchie à la fois.
On note : → ou : à partir du marquage Mi , le franchissement
de la séquence S aboutit au marquage Mj.

T1T2 et T1T3 sont deux séquences de franchissement:

→ et →
avec 0010 et 0001
 L'ensemble des marquages accessibles est l'ensemble des marquages Mi qui
peuvent être atteint par le franchissement d'une séquence S à partir du
marquage initial M0. On le note *M0
 On utilise le graphe de marquages quand le nombre de marquages
accessibles est fini.
• Un RdP autonome décrit le fonctionnement d'un système dont les instants de
franchissement ne sont pas connus ou indiqués.

Le moment de passage de l'été à l'automne est

inconnu.

• Un RdP non autonome décrit le fonctionnement d'un système dont l'évolution

est conditionnée par des événements externes ou par le temps. Un RdP non
autonome est synchronisé et/ou temporisé.
T1

Moteur Moteur a
Rdp non autonome car le franchissement
en marche l’arret
de T1 est conditionné par l’événement E.
E1: ordre d’arrêt E2: ordre de marche
T2
1.9 Les caractéristiques essentielles
 RdP borné, RdP sauf
◦ Une place Pi est dite bornée pour un marquage initial M0 si pour
tout marquage accessible, le nombre de marques dans Pi est fini
◦ Un RdP est borné pour un marquage initial M0 si toutes les
places sont bornées pour M0.
◦ RdP sauf, si pour chaque place contient au plus une marque

 Vivacité et Blocage
◦ Une transition Tj est vivante si pour tout marquage accessible
Mi, il existe une séquence S qui contient la transition Tj
◦ Un RdP est vivant pour un marquage initial M0 si toutes les
transitions sont vivantes
◦ Une transition est quasi-vivante, s’il existe une séquence de
franchissement qui contient Tj a partir de M0.
◦ Un blocage (état puit) est un marquage tel qu’aucune transition
n’est validée
◦ Les propriétés quasi vivacité et blocage sont indépendante
 2-1 Graphe d'état
Un réseau de Pétri non marqué est un graphe d'état si et seulement si toute
transition a exactement une seule place d'entrée et une seule place de sortie.

Chacune des transitions T1, T2, T3, T4 et T5 possède

une seule place d'entrée et une seule place de sortie.

 2-2 Graphe d'événement

Un RdP est un graphe d'événement si et seulement si chaque place possède
exactement une seule transition d'entrée et une seule transition de sortie.
 2-3 RdP sans conflit
Un Rdp sans conflit est un réseau dans lequel chaque place a au plus une transition de
sortie. Un RdP avec conflit est un réseau qui possède donc une place avec au moins
deux transitions de sorties. Un conflit est noté: [Pi , {T1,T2,…,Tn}] ; avec T1,T2,…,Tn
étant les transitions de sorties de la place Pi .

[P1 , {T1,T2}]

 2-4 RdP à choix libre

Un RdP à choix libre est un réseau dans lequel pour tout conflit [Pi , {T1,T2,…,Tn}]
aucune des transitions T1,T2,…,Tn ne possède aucune autre place d’entrée que Pi .
 Il est tel que pour tout conflit [Pi , {T1,T2,…,Tn}] toutes les transitions
T1,T2,…,Tn ont le même ensemble de places d’entrée.

 Il est tel que s’il existe une transition Tj et une place Pi qui est à la fois place
d’entrée et place de sortie de Tj alors Tj a au moins une autre place d’entrée,
 2-5 RdP simple
Un Réseau de Pétri simple est un RdP dans lequel chaque transition ne peut être
concernée que par un conflit au plus.

 2-6 RdP pur

Un RdP pur est un réseau dans lequel il n’existe pas de transition ayant une place
d’entrée qui soit à la fois place de sortie de cette transition.
 2-7 RdP généralisés
Un RdP généralisé est un RdP dans lequel des poids (nombres entiers strictement
positifs) sont associés aux arcs.
Si un arc ( Pi,Tj ) a un poids k : la transition Tj n'est franchie que si la place Pi
possède au moins k jetons. Le franchissement consiste à retirer k jetons de la place
Pi.
Si un arc ( Tj,Pi ) a un poids k : le franchissement de la transition rajoute k jetons à
la place Pi.
Lorsque le poids n’est pas signalé, il est égal à un par défaut.
 2-8 RdP à capacités
Un RdP à capacités est un RdP dans lequel des capacités (nombres entiers
strictement positifs) sont associées aux places. Le franchissement d’une
transition d’entrée d’une place Pi dont la capacité est cap(Pi) n’est possible que
si le franchissement ne conduit pas à un nombre de jetons dans Pi qui est plus
grand que Cap(Pi).

Le franchissement de T1 conduit à 3 jetons dans P2 d'où T1 ne peut plus être

franchie.
 Tout RdP à capacité peut être transformé en RdP ordinaire. Pour transformer
le RdP à capacité ci-dessous en RdP ordinaire, il suffit de supprimer la
capacité de la place Pj est d’ajouter une place Pj1 qui est place d’entrée de Ti
et place de sortie de Tj ; la capacité de la place Pj est alors limitée par le
fonctionnement du RdP.
 Exemple
 Le fonctionnement du RdP ordinaire considéré précédemment est détaillé
ci-dessous. La place P2 ne peut contenir qu’un maximum de 4 jetons.
 2-9 RdP à priorités
Dans un tel réseau si on atteint un marquage tel que plusieurs transitions sont
franchissables, on doit franchir la transition qui a la plus grande priorité.

Avant franchissement : Après franchissement :

Un arc inhibiteur est un arc orienté qui par d’une place P pour aboutir à une
transition t. Son extrémité est marquée par un petit cercle. L’arc inhibiteur entre la
place P et la transition t signifie que la transition t n’est validée que si la place P ne
contient aucune marque. Le franchissement consiste à retirer une marque dans
chaque place d’entrée de t à l’exception de P, et à ajouter une marque dans chaque
place de sortie de t. On utilise aussi les expressions test à zéro et RdP étendus .
A partir d’un marquage initial, le marquage
d’un RdP peut évoluer par franchissement de
transition; et s’il n’y a pas de blocage, le
nombre de franchissements de transitions est
illimité. Néanmoins, on ne pourra pas atteindre
n’importe quel marquage et on ne pourra pas
franchir n’importe quelle séquence de
transitions. Des invariants permettent de
caractériser certaines propriétés des
marquages accessibles et des transitions
franchissables, quelle que soit l’évolution.
3-1Composante conservative
Lorsqu’on considère l’exemple des 4 saisons, modélisé par le RdP , on peut noter que la somme du
nombre de marques présentes dans le RdP à un instant donné est toujours égal à un (conservation du
nombre de marques) : M(P1) +M(P2) +M(P3) +M(P4) = 1:
Cette égalité exprime qu’on ne peut avoir qu’une saison à la fois. D’autre part, elle implique que
∀ ∈ 1, 2, 3, 4 , 1. Le RdP est donc sauf.
Dans l’exemple de l’atelier de coupe simplifié présenté Figure ci-contre,
on a :
M(P2) +M(P3) +M(P4) = 4 et M(P1) +M(P3) = 1
M(P2) est le nombre de commandes en attente, M(P3) le nombre de
commande traitée par la machine de coupe et M(P4) celui qui ont été
traitées et stockées. Le premier invariant indique donc que le nombre total
de commandes dans l’atelier quelque soit sa forme reste constant. M(P1)
vaut 1 si la machine de coupe est disponible et M(P3) vaut 1 si la machine
de coupe traite une commande. Cet invariant indique donc que soit la
machine de coupe est disponible, soit elle traite une commande. On peut
interpréter cela comme une capacité limitée au niveau de la place P3 : elle
ne peut contenir qu’une marque au maximum.

Définition Soit R un Réseau de Petri et P l’ensemble de ses places. On a un invariant de marquage s’il
existe un ensemble de places P’Õ P et un vecteur d’entiers naturels appelé vecteur de pondérations q
tels que :
∀ ∈∗ ,
∈
P’ est appelé composante conservative. Un RdP est conservatif si et seulement si P’ = P.
Le RdP 4 saisons est conservatif.
Remarque La propriété “composante conservative” est indépendante du marquage initialM0. Par contre,
la valeur de la constante dépend de M0.
3-2 Composante répétitive
Il s’agit ici d’étudier le comportement cyclique de l’évolution de certains
RdPs. Dans l’exemple des 4 saisons, les séquences franchissables à partir
du marquage initial
M0 =[1 0 0 0]T
sont : T1, T1T2, T1T2T3, T1T2T3T4, etc.. T1T2T3T4 est une séquence qui
partant de M0 ramène à l’état initial : M0 [T1T2T3T4 > M0
Elle pourra donc être répétée indéfiniment.
Définition On appelle séquence répétitive stationnaire, une séquence de
franchissements S telle que : M0 [S > M0:
La séquence est dite complète si elle contient toutes les transitions du RdP.
On appelle séquence répétitive croissante, une séquence de
franchissements S telle que : M0 [S > M’0 avec M’0 > M0:
On appelle séquence répétitive décroissante, une séquence de
franchissements S telle que : M0 [ S > M ’’0 avec M0 > M ’’0
On appelle composante répétitive l’ensemble T’ des transitions de T
apparaissant dans la séquence S. Le RdP est dit répétitif si T = T’.
Propriété Si S est une séquence répétitive pour la condition initiale M0 alors
c’est aussi une séquence répétitive pour le marquage initial M’0¥ M0.
Recherche des propriétés :
Après avoir présenté les propriétés que peuvent posséder certains
réseaux, il importe maintenant de savoir comment on va pouvoir
trouver si tel réseau présente telle ou telle propriété. Il existe
principalement 3 classes de méthodes pour rechercher les propriétés
d’un RdP.
 Etablissement du graphe des marquages ou de l’arborescence de
couverture. C’est la méthode de base.
 méthodes basées sur l’algèbre linéaire. Il s’agit de résultats
puissants et élégants.
 méthodes de réductions des RdP. Les réductions ne donnent pas des
RdP équivalents, mais elles permettent de préserver certaines
propriétés, pour une analyse plus facile par les méthodes
précédentes.
 4-1 GRAPHE DES MARQUAGES ET ARBRES DE COUVERTURE
Le graphe des marquages est un graphe dont les nœuds correspondent à un
marquage du RdP et les arcs, des franchissements de transitions.
Exemple :

Sur ce graphe des marquages, on peut trouver toutes les propriétés de ce RdP. On
voit notamment que ce RdP est borné, sauf, vivant, réinitialisable, que T1T3T2T4 et
T1T2T3T4 sont des séquences répétitives (donc le RdP est répétitif) et que
2.m1+m2+m3+m4+m5 = 2 (donc le RdP est conservatif).
Un arbre de couverture est un graphe particulier dans lequel il n’y a pas de boucle ni
de circuit.
Algorithme de construction de l’arbre de couverture.
Pas 1 : A partir du marquage initial M0, on indique toutes les transitions validées et
les marquages successeurs correspondants. Si un de ces marquages est strictement
supérieur à M0, on met w pour chacune des composantes supérieures aux
composantes correspondantes de M0.
Pas 2 : Pour chaque nouveau marquage Mi de l’arbre, on fait soit le pas 2.1 soit le
pas 2.2
Pas 2.1 : S’il existe sur le chemin de M0 à Mi (ce dernier exclu) un marquage Mj =
Mi, alors Mi n’a pas de successeur.
Pas 2.2 : S’il n’existe pas de marquage Mj = Mi sur le chemin de M0 à Mi, alors on
prolonge l’arbre en ajoutant tous les successeurs de Mi. Pour chaque successeur Mk
de Mi :
 (a) une composante w de Mi reste une composante w de Mk ;

 (b) s’il existe un marquage Mj sur le chemin de M0 à Mk tel que Mk>Mj, alors on
met w pour chacune des composantes supérieures aux composantes de Mj.
Figure 1.27. Arborescence de couverture
et graphe de couverture.
Exemple (figures 1.27 a et b) :
 Pas 1. Mo [T1Ú M1

 Pas 2.2 pour M1

M1 [T2Ú M2
M1 [T3Ú (l, 0, 1). Comme (1, 0, 1) > (1, 0, 0) = M0, on écrit
M1 [T3Ú (0,0, w)= M0+
 Pas 2.2 pour M2 : aucune transition validée, c'est un blocage.

 Pas 2.2 pour M0+

M0+ [T1Ú (O, l, w) = M1+

 Pas 2.2 pour M1+

M1+ [T2 Ú (0, 0, w) =M2+

M1+ [T3 Ú (1, O, w) =M0+
 Pas 2.2. pour M2+ : aucune transition validée, c'est un blocage.

 Pas 2.1. pour M0+. Sur le chemin correspondant aux transitions

T1T3T1T3 depuis M0, on a déjà rencontré le même marquage
M0+.
L'arborescence de couverture obtenue par la procédure précédente
contient toujours un nombre fini de nœuds. On peut obtenir un
graphe de couverture (càd un graphe de couverture des marquages
accessibles) en fusionnant les nœuds de l'arborescence de
couverture qui correspondent au même "marquage", Sur la figure
1.27.b, il y a deux nœuds correspondant à M0+. Si on les fusionnent
on obtient le graphe de couverture de la figure 1.27.c.
A partir de l'arborescence de couverture de la figure 1.27.b, ou du
graphe de couverture de la figure 1.27.c, on peut obtenir un certain
nombre de renseignements: les places P1 et P2 sont bornées, mais
pas P3 : il y a une infinité de blocages qui correspondent à M2 et à
M2+ ; le RdP est quasi vivant. La construction de l'arborescence de
couverture constitue donc un algorithme qui permet de décider si
un RdP est borné: on dit que la propriété de réseau borné est
décidable. Cependant, pour un RdP non borné, l'arborescence de
couverture ne suffit pas à résoudre le problème de l'accessibilité
(càd, étant donné un marquage, est-il accessible ?), et le problème
de la vivacité. En effet, une partie de l'information est perdue en·
utilisant le symbole « w », L'accessibilité et la vivacité sont
également décidables, mais par des algorithmes plus compliqués.
Nous allons maintenant introduire un certain formalisme dans la définition des
réseaux de Petri, et certaines de leurs propriétés. Cette section s'applique aussi
bien aux réseaux de Petri généralisés qu'aux RdP ordinaires. L'expression réseau
de Petri (sans précision explicite) pourra donc s'appliquer à l'un ou l'autre type.
 a) Notations et définitions
Définition1. Un RdP ordinaire non marqué est un quadruplet Q = <p, T, Pré, Post>
tel que :
 P = {P1, P2, ..., Pn} est un ensemble fini et non vide de places;

 T = {T1, T2, ••• , Tm} est un ensemble fini et non vide de transitions ;

 P ⋂ T =∅, c'est-à-dire que les ensembles Pet T sont disjoints;

 Pré: Px T → {0,1} est l'application d'incidence avant;

 Post: Px T → {0,1} est l'application d'incidence arrière.

• Pré(Pi,Tj) est le poids de l'arc Pi → Tj. Ce poids est 1

si l'arc existe et 0 sinon. Par exemple, sur la figure
ci-contre, on a Pré(P1, T1) = 1 et Pré(P1,T4) =0.
• Post(Pi,Tj) est le poids de l'arc Tj → Pi. On a
Post(P3,T1) = 1 et Post(P3, T2) = 0.
"Pré" et "Post" sont donc relatifs à la transition Tj du
couple (Pi, Tj).
Définition 2. Un RdP généralisé non marqué est défini
comme un RdP ordinaire non marqué, sauf que:
Pré: P x T→N
Post: P x T →N

Par exemple sur la figure ci-contre. on a Pré(P1, T1) = 3 et

Post(P4,T1) = 2. Ces arcs ont des poids supérieurs à 1.
On utilisera les notations suivantes:
°Tj = {Pi ∈ P I Pré(Pi, Tj) > 0} = ensemble des places d'entrée de Tj
T°j = {Pi ∈ P I Post(Pi,Tj) > 0} = ensemble des places de sortie de Tj
°Pi = {Tj ∈ T I Post(Pi,Tj) > 0} = ensemble des transitions d'entrée de Pi
P°i = {Tj ∈ T I Pré(Pi,Tj) > 0} = ensemble des transitions de sortie de Pi

Définition 3. Un RdP marqué est un doublet R =<Q. M0> dans lequel Q est un RdP
non marqué et M0 un marquage initial.
Les conditions de validation peuvent s'exprimer maintenant de la façon suivante: la
transition Tj est validée pour un marquage M si et seulement si M(Pi) ¥ Pré(Pi,Tj) pour
tout Pi ∈ °Tj.
On appelle matrice d'incidence avant la matrice W- =[W-ij ] ,où W-ij =pré(Pj,Tj)
et la matrice d'incidence arrière la matrice W+ =[W+ij ] , où W+ij =Post(Pj,Tj).
On appelle matrice d'incidence la matrice w = W+ - W- =[Wjj ].
Dans ces matrices les transitions représentent les colonnes et les places
représentent les lignes.
 Exemple

Remarque: Si un RdP est pur. sa matrice d'incidence

permet de construire le RdP. Si un RdP est impur,
on ne peut pas reconstituer le RdP à partir de sa
matrice d'incidence. En effet, si le franchissement
d'une transition retire et ajoute des marques dans
une même place. la matrice d'incidence ne contient
que la différence (on a donc une perte
d'information sur le RdP).
 b) Equation fondamentale
 Soit S une séquence de franchissement réalisable à partir d'un marquage
Mi : Mi [S > Mk

 Soit S le vecteur caractéristique de la séquence S : c'est un vecteur de dimension

m égale au nombre de transitions dans le réseau. Sa composante numéro j
correspond au nombre de fois où la transition Tj est franchie dans la séquence S.

 Exemple si S=T2T4T1T4T2T4 alors S=[1, 2, 0, 3]T

 Si la séquence de franchissement S est tel que Mi [S > Mk alors l'équation

fondamentale correspondante s'écrit :

∗
 Soit la séquence S= T1T2 donc S =[1, 1, 0, 0]T

1 1 0 0 1
0 1 1 0 0 1
0 0 1 0 ∗ 1
0
0 0 1 0 1
0 0
0 0 1 1
 Remarque 1. On dira que S. est un vecteur caractéristique "possible" s'il lui
correspond au moins une séquence de franchissements S, à partir d'un
marquage Mi. Tous les vecteurs S dont les composantes sont des entiers
positifs ou nuls ne sont pas possibles. Par exemple, S = (0, 1, 0, 1) n'est pas
possible à partir du marquage M1 de la figure précédente. En effet, ni la
séquence T2T4 ni la séquence T4T2 ne sont possibles à partir de M1 .

 Remarque 2. A un vecteur caractéristique possible S plusieurs séquences de

franchissements peuvent correspondre. Par exemple à S=(0, 1, 1, 0), il
correspond deux séquences S possibles à partir du marquage M1 de la figure
précédente. Ces séquences de franchissements sont T2T3 et T3T2 (la
réciproque n'est pas vraie. c'est-à-dire que deux séquences conduisant au
même marquage Mk à partir d'un marquage Mj n'ont pas nécessairement le
même vecteur caractéristique). D'après l'équation fondamentale, deux
séquences de franchissements qui ont Le même vecteur caractéristique
conduisent au même marquage.
  c) Composantes conservatives et invariants de marquage
Soit F un vecteur de pondération des places F = (q1, q2, …, qn) tel que chaque qi est
un nombre entier positif ou nul. Soit P(F) l’ensemble des places dont le poids n’est
pas nul. P(F) est une composante conservative si et seulement si FT.W = 0.
Le vecteur F est appelé un P-semi-flot.
Dans notre exemple, pour F= (1,1,0,1,0), FT.W = 0 donc P(F) = {P1, P2, P4} est une
composante conservative. L’invariant linéaire de place est : m1 + m2 + m4 = 1. Il
existe un autre P-semi-flot pour cet exemple : G = (1, 0, 1, 0, 1).
Propriété : Si F1 et F2 sont deux P-semi-flots d’un même RdP, alors :
∀(a,b) ∈ℕ, a.F1 +b.F2 est un P-semi-flot.
Dans notre exemple, F+G = (2, 1, 1, 1, 1) est un P-semi-flot. Comme toutes les
places sont concernées par ce P-semi-flot, ce RdP est conservatif.
Propriété : Soient P(F) une composante conservative et F = (q1, q2, …, qn) le vecteur
pondération correspondant. Toutes les places de P(F) sont bornées et l’on a : M(Pi)
≤ (FT.M0)/qi.

1 0 0 1
1 1 0 0
1 0 1 0
0 1 0 1
0 0 1 1
 d) Composantes répétitives et invariants de franchissement

Soit S une séquence de franchissement et T(S) l’ensemble des transitions qui

apparaissent dans cette séquence. T(S) est une composante répétitive si et
seulement si W.S = 0. Le vecteur S est appelé un T-semi-flot. T(S) est une
composante répétitive croissante si W.S > 0. Remarque : tout T-semi-flot ne
correspond pas forcément une composante répétitive car il ne correspond pas
nécessairement à une séquence de franchissement.

Pour ce RdP, donnez la matrice W, un

P-semi-flot et un T-semi-flot, s’il y en a.
Pour les rdp ci-dessus établir l’arbre de couverture et donner les
P-semi-flots et les T-semi-flots s’ils existent
4-3 Méthodes de réduction
La construction du graphe des marquages est certes une méthode efficace pour
trouver les propriétés d'un RdP de taille modeste, mais ce peut être très long et
fastidieux pour un RdP qui a de nombreux marquages accessibles.

L'utilisation de l'algèbre linéaire devient également difficile lorsque la taille du RdP

étudié s'accroît. Nous allons maintenant présenter des méthodes de réduction qui
permettent de transformer un RdP en un autre RdP plus simple, en préservant
certaines propriétés du réseau initial. Mais attention. les réseaux simplifiés ne sont
pas des réseaux "équivalents" : il ne faut pas leur chercher une "interprétation" !

Nous présentons d'abord des réductions qui préservent les propriétés de RdP vivant
et RdP borné, puis des réductions préservant les invariants de marquage. Nous
donnerons des définitions informelles et des explications intuitives, qui sont
généralement suffisantes dans les cas pratiques. Le lecteur souhaitant avoir des
précisions pourra consulter les références qui sont données.

Ces méthodes sont présentées graphiquement pour une meilleure compréhension

(n'est-ce pas un des grands intérêts des réseaux de Petri ?). Elles peuvent
naturellement être programmées car applicables de façon algorithmique.
4.3.1. Préservation des propriétés vivant et borné
Les propriétés qui apparaissent dans cette section ont été démontrées par G.
Berthelot. Nous les présentons pour des RdP ordinaires. Elles peuvent
s'appliquer aux RdP généralisés moyennant quelques nuances et adaptations.

a. Réduction R1 : substitution d'une place

Une place Pi peut être substituée si elle remplit les trois conditions suivantes:
1) les transitions de sortie de Pi n'ont pas d'autres places d'entrée que Pi
(c'est-à-dire que tout franchissement d'une transition d'entrée de Pi
implique, tôt ou tard, le franchissement d'une transition de sortie de Pi) ;
2) il n'existe pas de transition Tj qui soit à la fois transition d'entrée et
transitions de sortie de Pi ;
3) au moins une transition de sortie de Pi n'est pas une transition puits (c'est-
à-dire qu'il existe Tk ∈ Pi o tel que Tk0 n'est pas vide).
Sur la partie gauche de la figure1.31.a, on voit que si la transition T1 est franchie,
alors la transition T2 le sera tôt ou tard parce qu'il n'y a aucun autre arc arrivant sur
T2 que celui qui vient de P2. On peut alors substituer à la place P2 et aux deux
transitions (d'entrée et de sortie) une seule transition appelée T12. La figure b
présente un cas similaire mais en montrant qu'il n'y a pas de restriction sur la
transition T1. En effet, les places d'entrée de T1 sont les places d'entrée de T12 et si
T1 a d'autres places de sortie que P2, ce sont également des places de sortie de T12•
On notera aussi que la place P2 est marquée. Comme cette marque doit
nécessairement arriver dans P3, on la met dans cette place après la substitution (le
mot suppression serait peut-être mieux adapté que substitution, qui est
habituellement utilisé).

Figure 1.31. Cas simples de substitution de place.

On voit sur la figure 1.32.a
que toute marque arrivant
en P3 doit passer dans P4,
qu'elle vienne de P1 ou de
P2. La substitution consiste à
mettre une transition T13 qui
correspond à la séquence de
franchissements T1T3, et la
transition T23 qui
correspond à la séquence de
franchissements T2T3.

Sur la figure 1.32.b, une

marque arrivant dans P2
passera tôt ou tard soit dans
P3, soit dans P4. L'application
de la réduction R1 conserve
cette propriété.
Les transitions T12 et T13
correspondent aux
séquences de
franchissements T1T2 et Figure 1.32. Substitution d'une place à 2 entrées ou
T1T3, respectivement. 2 sorties.
Sur la figure 1.33.a, une marque dans P3 peut provenir soit de P1 soit de P2, et
aboutir soit dans P4,soit dans P5. La figure 1.33.b représente le réseau après
substitution, en considérant tous les cas. Par exemple la transition T13 entre P1 et P4
correspond à la séquence de franchissements T1T3 .
Il va de soi que, dans ce cas général, les transitions T1 et T2 peuvent avoir d'autres
places d'entrées et/ou de sortie. Après substitution, elles apparaîtront dans le RdP,
comme sur la figure 1.31.b. La seule contrainte pour effectuer la substitution est
que les transitions de sortie de P3, soit T3 et T4, n'aient pas d'autres places
d'entrées.

Figure 1.33. Substitution d'une

place qui a plusieurs entrées et
plusieurs sorties.
Il reste un cas à considérer, c'est celui où la place donnant lieu à substitution est
marquée. Si elle n'a qu'une transition de sortie, on met la marque dans la place
suivante (figure 1.31.b). En revanche, s'il y a plusieurs transitions de sortie, il faut
considérer tous les cas possibles. Par exemple sur la figure 1.34, la marque qui est
dans P2 avant la substitution pourrait aboutir soit dans P3 soit dans P4. Il faut
considérer les deux cas, c'est-à-dire qu'il faut étudier 2 réseaux différents à partir
de maintenant. Les propriétés qui se conservent par la réduction R1 ne seront vraies
pour le réseau initial que si elles sont vraies pour les deux réseaux finals.

Figure 1.34. Substitution d'une place qui est marquée.

 Propriétés conservées par la réduction R1. Chacune des propriétés suivantes:
borné, sauf, vivant, quasi vivant, sans blocage, avec état d'accueil, conservatif, est
vérifiée pour le RdP réduit si et seulement si elle l'est pour le RdP initial
(ordinaire).
Insistons sur le fait que les réductions provoquent une perte d'information: si un
RdP est borné, ou possède un état d'accueil, on ne sait pas nécessairement quelle
est cette borne ou quel est l'état d'accueil. Cette remarque est vraie pour les
réductions RI à R4 .
b. Réduction R2: place implicite
Une place Pi est implicite si elle remplit les conditions suivantes:
1) le marquage de cette place n'est jamais un obstacle au franchissement de ses
transitions de sortie (c'est-à-dire que si Tj est une transition de sortie de Pi alors,
quand M(Pk) ¥ Pré(Pi. Tj) pour toutes les places Pk de °Tj autres que Pi • alors M(Pi)
¥Pré(Pj, Tj ) aussi), et
2) son marquage peut se déduire du marquage des autres places, par la relation
suivante, où Uk est un nombre rationnel positif ou nul et β un nombre rationnel :

La réduction R2 consiste à supprimer une place implicite et les arcs correspondants.

La place P2 de la figure 1.35.a est implicite. Condition 1 : P2 est toujours marquée
et la validation de T1 ne dépend donc que du marquage de P1. Condition 2 :
évidemment vérifiée puisque son marquage est constant. La réduction R2 donne
donc le RdP de la figure 1.35.b. Attention, cette réduction ne serait pas licite si la
place P2 n'était pas marquée (on rendrait vivante ou quasi vivante une transition
qui ne l'est pas initialement).

Figure 1.35. Premier cas de place implicite.

Sur la figure 1.36.a, la place P2 est une place implicite. Condition 1 : cette place n'est
place d'entrée que de T3• Pour franchir T3, il faut une marque dans P3, donc il a fallu
franchir T2 avant de pouvoir franchir T3• Pour franchir T2, il fallait une marque dans P1 et
cette marque ne pouvait provenir que du franchissement de T1. Or, le franchissement de
T1 met une marque dans P2, et il n'y a aucune autre sortie de P2 que la transition T3•
Donc, s'il y a une marque dans P3, il y en a aussi une dans P2• Condition 2 : le
raisonnement précédent conduit à Mj (P2) =Mj(P1) + Mj(P3) pour tout marquage Mj•
L'application de la réduction R2 à ce réseau conduit au RdP de la figure 1.36.b.

Sur la figure 1.36.c. la place P2 est aussi une place implicite, a fortiori. Le raisonnement
précédent permet de montrer que lorsqu'il y a une marque dans P3• il yen a trois dans
P1, donc la condition 1 est satisfaite. La condition 2 l'est aussi car Mj (P2) =Mj(P1) + Mj
(P3) + 2. pour tout marquage Mj.

Figure 1.36. Exemples de place implicite, et de places

ne remplissant pas les conditions.
La figure 1.36.d montre un cas où la condition 1 est satisfaite, mais pas la condition
2 parce que la transition T4 est une transition source (sans étape d'entrée). Sur la
figure 1.36.e, la condition 2 est satisfaite, mais pas la condition 1 parce qu'il n'y a
pas de marque dans P2 alors que P3 contient une marque. Dans ces deux cas, la
place P2 ne peut pas être supprimée, sous peine de ne pas conserver certaines
propriétés du réseau initial.

Figure 1.36. Exemples de place implicite,

et de places ne remplissant pas les conditions.

Propriétés conservées par la réduction R2•

Chacune des propriétés suivantes: borné. vivant. quasi vivant. sans blocage.
avec état d'accueil. conservatif, est vérifiée pour le RdP réduit si et seulement si
elle l'est pour le RdP initial (ordinaire ou généralisé). Si le RdP est sauf après
réduction, le RdP initial peut ne pas l'être (exemple figure 1.36.c).
c) Réduction R3 : transition neutre

Une transition Tjest neutre si et seulement si l'ensemble de ses places d'entrée est
identique à l'ensemble de ses places de sorties, soit °Tj = T°j. On peut supprimer une
transition neutre et ses arcs entrants et sortants, si et seulement s'il existe une
transition Tk ≠Tj, telle que Post(Pi, Tk) ¥ Pré(Pi, Tj} pour toute place Pi ∈ °Tj.

Figure 1.37.
Transition neutre.

Sur la figure 1.37.a, la transition T5 est neutre, c'est-à-dire que son franchissement
ne modifie pas le marquage (le réseau n'est pas pur). Cette transition peut être
supprimée parce que la transition T1 est telle que: Post(P1,T1) = Pré(P1 T5) et
Post(P2, T1) = Pré(P2,T5). La réduction R3 donne le RdP de la figure 1.37.b.
Propriétés conservées par la réduction R3. Chacune des propriétés suivantes:
borné, sauf, vivant, quasi vivant, sans blocage, avec état d'accueil, conservatif, est
vérifiée pour le RdP réduit, si et seulement si elle l'est pour le RdP initial (ordinaire ).
d) Réduction R4 : transitions identiques
Deux transitions Tj et Tk sont identiques si elles ont le même ensemble de places
d'entrées et le même ensemble de places de sorties, soit °Pj =°Pk et Pj°= P°k• On peut
alors supprimer l'une d'entre elles et les arcs correspondants.

Figure 1.38. Transitions identiques.

Sur la figure 1.38.a les transitions T1 et T2 sont identiques. La suppression de la

transition T2 donne le RdP de la figure 1.38.b.

Propriétés conservées par la réduction R4 .

Chacune des propriétés suivantes: borné, sauf. vivant, quasi vivant, sans blocage.
avec état d'accueil. conservatif, est vérifiée pour le RdP réduit si et seulement si elle
l'est pour le RdP initial (ordinaire).
 Exemple. Ces règles de réductions sont illustrées sur la figure 1.39. Sur la figure a.
on peut appliquer la règle R1 à la place P2 parce que sa seule transition de sortie n'a
pas d'autre place d'entrée (on aurait aussi pu le faire pour P3• mais on ne fait qu'une
réduction à la fois). On obtient la figure b. Sur ce RdP, la place P4 est une place
implicite (R2). On obtient la figure c sur laquelle on applique R1 pour P3.

Puis la réduction R1 est à

nouveau appliquée à la
figure d. Sur la figure e, la
transition T1234 est neutre.
Néanmoins. on ne peut pas
faire la réduction R3 parce
qu'il n'y a pas d'autre
transition Tk qui ait P1
comme place de sortie. On
voit que le RdP de la figure e
est borné, vivant, sans
blocage, qu'il a un étal
d'accueil. et qu'il est
conservatif. Donc, le RdP
initial a également toutes
ces propriétés.

Figure 1.39. Exemple de réduction d'un RdP (R1 à R4).

4.3.2 Préservation des invariants
J. Martinez et M. Silva d'une part, et J.-M. Toudic d'autre part, ont proposé un
algorithme efficace qui permet d'obtenir toutes les composantes conservatives
minimales, et parfois d'autres composantes conservatives non minimales (après
divers travaux, dont ceux de B. Berthomieu). Nous présentons une adaptation de ces
résultats sous forme de règles de réduction. Nous présentons ces réductions en
tenant compte du marquage initial, ce qui permet d'obtenir directement les
invariants de marquage. Néanmoins, on pourrait faire ces réductions sans tenir
compte du marquage ; on obtiendrait les P-semi-flots, qui correspondent à des
propriétés structurelles.
Les règles de réduction Ra et Rb s'appliquent à des RdP ordinaires. Elles sont très
souvent suffisantes en pratique. Toutefois il arrive que l'application de la règle Rb
transforme un RdP ordinaire en un RdP généralisé. Les règles R'a et R'b s'appliquent
aux RdP généralisés. Nous les présenterons en même temps que l'algorithme ci-
dessus mentionné.
[Link] Réseau de Petri ordinaire

Réduction Ra • Transition impure dans un RdP ordinaire.

Soit Tj une transition impure. C'est-à-dire qu'il existe au moins une place Pi et deux
arcs Pi → Tj et Tj → Pi La réduction relative à cette transition impure consiste à :
1) supprimer les arcs Pi → Tj et Tj → Pi,
2) supprimer la transition Tj si elle est isolée (c'est-à-dire si elle n'a plus ni place
d'entrée ni place de sortie).
Cette réduction est illustrée sur la figure 1.40. La figure a présente un cas où la
transition T1 n'est pas isolée après la suppression des arcs P1 → T1 et T1 → P1 Sur la
figure b, la transition T1 devient isolée, et elle est donc supprimée.
Réduction Rb . Transition pure dans un RdP ordinaire.
La réduction relative à une transition pure Tj peut être faite ssi Tj a au moins une place
d'entrée et une place de sortie, c'est-à-dire que °Tj et T°j ne sont pas vides.
1) La transition Tj est supprimée.
2) A tout couple de places (Pi , Pk) tel que Pi E °Tj et Pk E T°j, on associe une place Pi + Pk
(le + symbolise l'union de ces places. Le nombre de marques dans Pi + Pk est la
somme des marques qui étaient initialement dans Pi et dans Pk.
3) Les transitions d'entrée de Pi + Pk sont les transitions d'entrée de Pi et les transitions
d'entrées de Pk , à l'exception de Tj. Les transitions de sortie de Pi + Pk sont les
transitions de sortie de Pi et les transitions de sortie de Pk , à l'exception de Tj.

Cette réduction est illustrée sur la figure 1.41. La figure a présente un cas simple où la
transition T2 est supprimée, tandis que les places P1 et P2 sont fusionnées en une place
P1 + P2• La figure b présente deux cas où la réduction n'est pas possible. La transition
T6 ne peut pas être supprimée parce qu'elle n'a pas de place de sortie. La transition T7
ne peut pas être supprimée parce qu'elle n'a pas de place d'entrée. La figure c
présente un cas plus général où la transition T3 a plusieurs places d'entrée, P1 et P2, et
plusieurs places de sortie, P3 et P4. A chaque paire composée d'une place d'entrée et
d'une place de sortie, on associe une place qui en est l'union. On a donc les places P1
+ P3, P1 + P4, P2 + P3 et P2 + P4. On voit que le nombre de marques dans P1 + P3, par
exemple, est la somme des marques initialement dans P1 et dans P3, soit deux.
Exemple.
Un exemple de réduction
préservant les invariants
de marquage est présenté
sur la figure 1.42.
La réduction Rb est
appliquée successivement
aux transitions T2, T3 et
T4 , puis la réduction Ra
est appliquée à T1.
On obtient deux
invariants qui sont :
ml + m2 + m4 =1
et
ml + m3 + ms =2.
Lorsqu'on ne peut plus appliquer ni la règle Ra, ni la règle Rb, le résultat est un
ensemble de cas similaires aux 4 cas présentés sur la figure 1.43 (ou éventuellement
un RdP généralisé). La figure a représente une composante conservative {P1, P2}
correspondant à l'invariant m1 + m2 =1. La figure b correspond à un ensemble de
places {P3, P4} qui contient initialement une marque, et qui peut se vider (sous réserve
que la transition T1 soit vivante dans le RdP initial, l'utilisation des règles Ra et Rb ne
le garantissant pas). L'ensemble des places {P5, P6 } correspondant à la figure c
contient initialement une marque. Ce nombre peut s'accroître de façon non bornée
(sous réserve que T2 soit vivante dans le RdP initial). Il y a donc au moins une des
places P5 ou P6 qui est non bornée. Sur la figure d, la place P7 + P8 peut se vider et se
remplir de façon non bornée (sous réserve que T3 et T4 soient vivantes dans le RdP
initial).
Remarque 1.14. Le graphe réduit peut dépendre de l'ordre de réduction. Ceci est
illustré sur la figure 1.44. Si la première réduction est relative à la transition T1, on
obtient un invariant m1 + m2 =1, et m3 ¥ 0 est non borné. Si la première réduction
porte sur T2, on obtient bien le même invariant m1 + m2 = 1, et m2 + m3 ¥ 1. Il y a
donc au moins une des places P2 et P3 qui n'est pas bornée (car T1 et T2 sont vivantes).
Comme m1 + m2 =1, c'est donc la place P3 qui n'est pas bornée. Il est intéressant de
noter que lorsqu'on fait une réduction Rb sur une transition qui n'a qu'une place
d'entrée et une place de sortie (transition T1 sur la figure 1.44) on ne duplique aucune
des places. On a donc intérêt à ne faire ces réductions Rb que sur de telles
transitions, quand cela est possible. On aura ainsi une interprétation plus simple des
places qui ne sont pas dans des composantes conservatives.

Remarque 1.15. Supposons qu'au cours du processus de réduction on rencontre la

situation suivante : il existe deux places Px et Py telles que Px contient toutes les
places composantes de Py (par exemple, Px =P1 + P2 + P3 et Py =P1 + P2). Alors on peut
supprimer la place Px et les arcs correspondants. En effet. ces deux places ont
nécessairement les mêmes transitions d'entrée et les mêmes transitions de sortie
(c'est-à-dire °Px =°Py et P°x =P°y) et toute composante conservative qui serait obtenue
à partir de Px serait au moins aussi grande qu'une composante conservative obtenue à
partir de Py. Cette simplification ne peut donc pas supprimer la possibilité d'obtenir
toutes les composantes conservatives minimales.
[Link]. Réseau de Petri généralisé
Nous allons maintenant aborder le cas de RdP généralisés, et d'abord présenter
l'algorithme déjà mentionné, en l'illustrant par la figure 1.45.

Algorithme 1.2. Recherche des P-semi-flots (Martinez et Silva)

Pas 1. Soit A la matrice unité de dimension n (nombre de places) et B = W
(matrice d'incidence). Construire la matrice [A | B].
Pas 2. Pour chaque indice j de transition Tj :
Pas 2.1. ajouter à la matrice [A | B] autant de lignes i qu'il y a de
combinaisons linéaires de deux lignes, à coefficients entiers positifs,
annulant l'élément (i, j) ;
Pas 2.2. éliminer de la matrice [A | B] les lignes i dont l'élément (i, j) n'est
pas nul.
Pas 3. Les P-semi-flots, donc les invariants de marquage, correspondent aux
lignes non nulles de A.
Exemple (figure 1.45).
Pas 1. On obtient la matrice de 4 lignes (P1 à P4) et 7 colonnes.
Pas 2.
Pas 2.1. Pour T1 : on ajoute la ligne marquée P1 + P2 qui est la somme des deux
premières lignes.
Pas 22 . Pour T1 : on supprime les lignes P1 et P2•
Pas 2.1 . Pour T2 : on ajoute la ligne marquée P3 + 2 P4 (poids 1 pour P3 et poids 2
pour P4).
Pas 22. Pour T2 : on supprime les lignes P3 et P4.
Pas 2.1. Pour T3 : on n'ajoute aucune ligne.
Pas 22. Pour T3 : on supprime la ligne P1 + P2•
Pas 3. Il reste seulement la ligne P3 + 2 P4, qui indique qu'il y a une composante
conservative {P3, P4} avec des poids respectifs 1et 2 pour ces deux places.

1 0 0 0 1 0 2
0 1 0 0 1 0 3
0 0 1 0 0 2 2
0 0 0 1 0 1 1
pour T1 1 1 0 0 0 0 1
pour T2 0 0 1 2 0 0 0 2
pour T3

Figure 1.45. Illustration de l'algorithme donnant les

P-semi-flots (donc les composantes conservatives).
Réduction R'[Link] impure.
Soit Tj une transition impure et Pi une place telle que l'arc Pi →Tj a un poids p et l'arc
Tj →Pi a un poids q.
1) Si P > q, donner le poids p -q à l'arc Pi →Tj et supprimer l'arc Tj →Pi
Si P =q, supprimer les deux arcs Pi →Tj et Tj →Pi
Si P < q, donner le poids q -P à l'arc Tj →Pi et supprimer l'arcPi →Tj
2) Supprimer la transition Tj si elle est isolée (c'est-à-dire sans aucune place
d'entrée ni de sortie).

Réduction R'b. Transition pure.

La réduction relative à une transition Tj peut être faite si et seulement si Tj a au
moins une place d'entrée et une place de sortie.
1) La transition Tj est supprimée.
2) A tout couple (Pi , Pk) tel que Pi ∈ °Tj et Pk ∈ T°j on associe une place définie
comme suit. Soit p le poids de l'arc Pi →Tj et q le poids de l'arc Tj →Pk . La place
associée à (Pi, Pk) est notée q Pi + p Pk. Le nombre de marques dans cette place
est la somme du nombre de marques qui étaient initialement dans Pi multiplié
par q, et du nombre de marques qui étaient dans Pk multiplié par p.
3) Les transitions d'entrée et de sortie de Pi (à l'exception de Tj) deviennent des
transitions d'entrée et de sortie de q Pi + p Pk, avec un poids qui est multiplié par
q. Les transitions d'entrée et de sortie de Pk (à l'exception de Tj) deviennent des
transitions d'entrée et de sortie de q Pi + p Pk avec un poids qui est multiplié par
p.
 Les règles de
réduction sont
illustrées sur la
figure 1.46, dans
un cas général, et
sur la figure
1.47 pour
l'exemple de la
figure 1.45.
Après les réductions
qui sont représentées
sur la figure 1.47, on
obtient le résultat
suivant. Il y a un
invariant qui est
m3 + 2 m4 = 2
(correspondant à P3 +
2 P4), et ml + m2 n'est
pas borné (la transition
T 3 était vivante). Ces
deux places ne sont
pas bornées.

Remarque 1.16. Pour

un RdP ordinaire,
R'a = Ra
et
R'b = Rb