Chapitre 3.

Les Réseaux de Petri

(RdP en abrégé)

3.1. Origine et domaines d'application

3.2. Présentation informelle
3.3. La formalisation
3.4. Exemple : un système de 2 équipements
interconnectés
3.5. Raffinement et composition
3.6. Quelques extensions…
3.1. Origine et domaines
d'application
…
 3.1. RdP : origine et domaines
d'application
Origine :
Idées de départ de Carl Adam Petri (thèse en 1962) :
– Un ensemble d'automates à états finis qui communiquent

– Avoir à la fois la représentation des automates

– Et celle des communications par les mêmes primitives

• communications asynchrones par échange de messages
• communication synchrones par rendez-vous, synchronisations,
ressources partagées

=> Graphes avec 2 types de nœuds « places » et

« transitions »
 3.1. RdP : origine et domaines
d'application
Domaines d'application :
– Systèmes de production, Autom. Prog. Ind., Grafcet
• Evaluation des performances, simulation à événements discrets

– Validation de protocoles de communication

– Systèmes temps réels, systèmes distribués, génie logiciel

– Systèmes d'information, gestion, interfaces homme-

machine

– Modèles de raisonnement, planification

3.2. Présentation informelle du
formalisme…
…
3.2. RdP : présentation informelle
• Le formalisme des réseaux de Petri est un outil permettant l'étude de
systèmes dynamiques et discrets.

• Il s'agit d'une représentation mathématique permettant la

modélisation d'un système.

• L'analyse d'un réseau de Petri peut révéler des caractéristiques

importantes du système concernant sa structure et son
comportement dynamique.

• Les résultats de cette analyse sont utilisés pour évaluer le système et

en permettre la modification et/ou l'amélioration le cas échéant.
3.2. RdP : présentation informelle
Démarche générale
 3.2. RdP : présentation informelle
Concepts de base
– Condition
• Une condition est un prédicat ou une description logique d'un état du système.
• Une condition est vraie ou fausse.
• Un état du système peut être décrit comme un ensemble de conditions.

– Evénement
• Les événements sont des actions se déroulant dans le système.
• Le déclenchement d'un événement dépend de l'état du système.

– Déclenchement, précondition, postcondition

• Les conditions nécessaires au déclenchement d'un événement sont les préconditions de
l'événement.
• Lorsqu'un événement se produit, certaines de ses pré-conditions peuvent cesser d'être
vraies alors que d'autres conditions, appelées postconditions de l'événement deviennent
vraies.
 3.2. RdP : présentation informelle
Concepts de base
P
– Condition = Place
t
– Evénement = Transition

– précondition = arc Place -> Transition

P
t1 t2

– postcondition = arc Transition -> Place

t

P1 P2
 3.2. RdP : présentation informelle
Concepts de base
– Satisfaction d'une Condition = Jeton dans une Place

P P
vrai faux

Remarque : on peut avoir un nombre quelconque non borné de jetons dans une
place
 3.2. RdP : présentation informelle
Concepts de base
– Condition de franchissement d'une transition = satisfaction de toutes les
places préconditions de la transition
P2 P2'
P1 P1'
t1 t1'
non franchissable franchissable

– Effet du franchissement d'une transition = satisfaction de toutes les places

postconditions de la transition

P P
avant franchissement
t t après franchissement

P2 P1 P2
P1
3.2. RdP : présentation informelle
Modélisation de systèmes avec ressources
– Pour certains systèmes, il est plus juste de raisonner en termes d'ensemble de
ressources, au sens large, qu'en termes de conditions-événements.
=> un jeton = une ressource
– Le nombre de jetons contenus dans une place reflète le nombre de ressources qu'elle
possède.
– Les jetons d'une place n'ont pas d'identité individuelle, autrement dit ils sont
indiscernables.
– Ces ressources sont consommées et produites par les événements du système.
– Les arcs entrants d'une transition peuvent être valués par un entier quelconque (non
nul)
=> valuation = nombre de jeton nécessaires dans la place pour franchir la transition
=> si k est la valuation d'un arc d'une place P vers une transition T, le tir de la transition T retire k
jetons dans la place P
– Les arcs sortants d'une transition peuvent être valués par un entier quelconque (non
nul)
=> valuation = nombre de jeton produits dans la place située après la transition
=> si k est la valuation d'un arc d'une transition T vers une place P, le tir de la transition T dépose
k jetons dans la place P
– Par défaut, les arcs sont valués par 1.
3.2. RdP : présentation informelle
Concepts de base
– Exemples
3 3 P2'
P2 2
P1 2 P1'
t1 t1'
non franchissable franchissable

avant franchissement P P
2 2
t t après franchissement
3 3
P2 P1 P2
P1
3.2. RdP : présentation informelle
Exemple…
une réaction chimique d'oxydo-réduction

C02
H2C204 2 H202

2 H+
2 2

e- 2 2
H2 0
 3.2. RdP : présentation informelle
Schémas particuliers

a b a b
b

indétermisme a ou b

indépendance a||b partage de ressource

séquence a;b (exclusion, conflit…)
 3.2. RdP : présentation informelle
Schémas particuliers

E
E
E

ackE

synchonisation a=b, sémaphore,

envoisynchrone envoi asynchrone
d’un message E d’un message E envoi asynchrone
d’un message E
avec acquittement
3.2. RdP : présentation informelle
• Notions complémentaires
T0

– Une transition-puit est une

transition ayant une sortie vide. P1

– Une transition-source est une P2

transition ayant une entrée

2
vide.
T1
– Une boucle est un circuit
constitué d'une seule place et P3
d'une seule transition. P4

– Un RdP sans boucle est dit pur

T2
2
P5
– Exemple :
• T0 est une transition-source.
• T3 est une transition-puit.
T3
3.2. RdP : présentation informelle
Exemple : les 5 philosophes

fourchette fourchette
gauche pense droite

mange

1 philosophe

=> composition par mise en commun des fourchettes

=> fusion des places « fourchette droite » du philosophe N et « fourchette
gauche » du philosophe N+1 (modulo 5)
3.2. RdP : présentation informelle
Exemple : les 5 philosophes

Philosophe 0 Philosophe 1 Philosophe 2 Philosophe 3 Philosophe 4

 3.3. La formalisation

3.3.1. Les bases de la formalisation

3.3.2. L’étude de la dynamique
3.3.3. L’étude de propriétés structurelles
 3.3. RdP : formalisation
• L'un des intérêts de ce formalisme, c'est la possibilité de vérifier
formellement des propriétés

• Nécessite le recours à la formalisation (matrice d'incidence, séquence de

franchissement, vecteur caractéristique, équation d'état)

• Propriétés structurelles (structure du réseau) et/ou comportementales

(évolution du réseau)
 3.3.1. Formalisation : les bases
Réseau de Petri: R = {P, T, Pre, Post}
– P = ensemble de places
– T = ensemble de transitions

– Pre = PxT  N places précédentes

Pre(p, t) = nombre de jeton nécessaire dans la place p
pour le franchissement de la transition t

– Post = PxT  N places suivantes

Post(p, t) = nombre de jeton produits dans la place p lors
du franchissement de la transition t

=> C = Post - Pre matrice d'incidence

 3.3.1. Formalisation : les bases
Réseau de Petri: R = {P, T, Pre, Post}
=> Représentation matricielle
 3.3.1. Formalisation : les bases
Réseau marqué: N = {R,M}
Le marquage d'un RdP R=(P, T, Pre, Post) est son état. Formellement, un
marquage est une application

M:PN

donnant pour chaque place le nombre de jetons qu'elle contient. Le

marquage initial est généralement noté M0.

Notation matricielle:
– Transitions en colonnes
– Places en lignes
– Marquage = vecteur colonne
 3.3.2. Formalisation : propriétés
dynamiques
Dynamique (sémantique) d'un RdP
– Transition t franchissable
• une transition t est franchissable ssi, pour toute place p,

M(p) > Pre(p, t)

– Franchissement d'une transition t

• Si une transition t est franchissable à partir du marquage M,
alors le nouveau marquage de toute place p est
M'(p) = M(p) - Pre(p, t) + Post(p, t)
= M(p) + C(p, t)
avec C = Post - Pre (matrice d'incidence)

on note M —t M‘
(tir de la transition t à partir du marquage M)
 3.3.2. Formalisation : propriétés
dynamiques
Dynamique (sémantique) d'un RdP
– Exemple
• t1 est franchissable car

Pre(., t1) = 2 < M0

0

• après le franchissement de t1
M = M0 - Pre(., t1) + Post(., t1)

2 1 1
2 1 0 5 0 1
= 3 - 0 + 0
0 6 4 7 3 0
0 0

2 2 5 5
= - + =
3 0 7 10
 3.3.2. Formalisation : propriétés
dynamiques
Dynamique (sémantique) d'un RdP
– Exemple

• calcul direct avec la matrice d'incidence

M = M0 + C(., t1)

2 1
3 -1 1
= 3 + 0 = 5
7 -3 -4 10
0

donne le même résultat

 3.3.2. Formalisation : propriétés
dynamiques
Dynamique (sémantique) d'un RdP : séquence
de transitions

T1 T2 T3 T4
est une séquence de
transitions
franchissables
 3.3.2. Formalisation : propriétés
dynamiques
Dynamique (sémantique) d'un RdP : séquence de transitions
Soit un RdP R=(P, T, Pre, Post) de marquage initial M0
Soit t1 t2 ... tn des transitions de T telles que
M0 —t1 M1 —t2 M2 … —tn Mn
alors, t1 t2 ... tn est appelée séquence de transitions franchissables
(successivement)

De plus
Mn = M + C . VsT
où Vs est le vecteur caractéristique de la séquence de transitions
s = t1 t2 ... tn
tel que Vs(t) donne le nombre d'occurrences de la transition t dans s
On note
M —s Mn
 3.3.2. Formalisation : propriétés
dynamiques
Equation d'état

Mf = M + C . VsT

Remarque :
s = s1 . s2 => Vs = Vs1 + Vs2
Vs1 = Vs2 => M + C . Vs1T = M + C . Vs2T même si s1s2
 3.3.2. Formalisation : propriétés
dynamiques
Dynamique (sémantique) d'un RdP : séquence
de transitions
Exemple :

T = {T1, T2, T3, T4}

VT2T3T4T1T3 = (1, 1, 2, 1)
 4.3.2. Formalisation : propriétés
dynamiques
Remarques importantes :
– ATTENTION ! Le vecteur caractéristique ne fait que compter le nombre
d'apparition des transitions. Il ne donne pas, comme la séquence, l'ordre
dans lequel celles-ci ont lieu.

T = {T1, T2, T3} V = (1, 2, 1)

Le vecteur V ci-dessus est le vecteur de comptage de toutes les séquences de

franchissement suivantes :

<T1, T2, T3, T2>, <T3, T1, T2, T2>, <T3, T2, T2, T1>,
<T1, T3, T2, T2>, <T1, T2, T2, T3>, …
 4.3.2. Formalisation : propriétés
dynamiques
Remarques importantes :
– ATTENTION ! L'équation d'état permet de calculer le marquage atteint après
franchissement d'une séquence de transitions. Elle ne permet pas de dire que
la séquence est franchissable !!
T1 T2 T3 T4
P1 P2 P3 P4 P5

La séquence <T1, T2, T3> est franchissable,

Les séquences <T2, T1, T3>, <T3, T2, T1>, <T2, T3, T1> ne le sont pas !
Elles ont pourtant même vecteur de comptage. L'équation d'état donnera
donc le même résultat pour les quatre.
 4.3.2. Formalisation : propriétés
dynamiques
Aperçu (incomplet et approximatif) des raisonnements faisables sur un RdP
– Le rôle de l'équation d'état est de matérialiser, en termes de jetons, l'évolution du RdP.
Elle représente l'outil qui va permettre de calculer le résultat du franchissement de
transitions. En tant que tel, elle est nécessaire. Il faut toutefois l'utiliser correctement,
en pas à pas.

Eq. Eq. Eq.

M0 M1 M2 M3
Etat Etat Etat

Pb Pb Pb

L'équation d'état peut signaler un non-franchissement. Une transition est franchissable

s'il y a suffisamment de jetons dans chacune de ses places en entrée. La matrice
d'incidence fournit le nombre de jetons produits par le déclenchement de chaque
transition.

L'équation d'état appliquée à une séquence réduite à une transition fournit le nombre
de jetons qui restent après « exécution » de cette transition.
=> Si ce nombre est négatif, alors la transition n'est pas franchissable.
(Attention : réciproque fausse)
 3.3.2. Formalisation : propriétés dynamiques
Aperçu… des raisonnements faisables…
– L'équation d'état peut également servir à autre chose. Il est possible de
calculer le marquage initial nécessaire pour franchir une séquence donnée et
arriver à un marquage donné. Le travail se fait, dans ce cas-là, « à l'envers ».
M0 = Mf - C . VsT
Eq. Eq. Eq.
M0 M1 M2 Mf
Etat Etat Etat
P1
P2
Pb Pb Pb
– Exemple : 2
Quel marquage initial pour le marquage final T1
Mf= [2, 5, 1, 4, 0] et la séquence <T1, T2, T2> P3
=> calcul de M2 P4

x 2 0 -1 3
y 5 -2 0 5 T2
0 2
M2 = z = 1 - 1 -1
1 => M2 = 2 P5
t 4 0 -1 5 Impossible :
u 0 0 2 -2 Mf inaccessible
par T2
 3.3.2. Formalisation : propriétés dynamiques
P1
P2

Aperçu… des raisonnements faisables… 2

T1
– Autre Exemple :
P3
Quel marquage initial pour le marquage final P4
Mf= [2, 5, 1, 4, 5] et la séquence <T1, T2, T2>
2 0 -1 3 T2
=> calcul de M2 5 -2 0 5 2
0 P5
M2 = 1 - 1 -1 = 2
1
4 0 -1 5
5 0 2 3
3 0 -1 4
5 -2 0 5
=> calcul de M1 0
M1 = 2 - 1 -1 1 = 3
5 0 -1 6
3 0 2 1
4 0 -1 4
5 -2 0 7
=> calcul de M0 1
M0 = 3 - 1 -1 = 2
0
6 0 -1 6
1 0 2 1
3.3.2. Formalisation : propriétés dynamiques
Aperçu… des raisonnements faisables…
– L'équation d'état peut également déterminer le marquage initial minimal
pour franchir une séquence donnée, sans se préoccuper du marquage final.

M0 + C . VsT > 0

Eq. Eq. Eq.

M0 M1 M2 Mf > 0
Etat Etat Etat

Pb Pb Pb
 3.3.2. Formalisation : propriétés dynamiques
P1
P2

2
Aperçu… des raisonnements faisables… T1

– Exemple : P3
P4
Quel marquage initial minimal permettant le franchissement
de la séquence <T1, T2, T2>
T2
=> calcul des contraintes sur M2 2
0 -1 0 P5
x x 1
y -2 0 0 y 0
0
M2 = z + 1 -1 > 0 => z > 1
1
t 0 -1 0 t 1
u 0 2 0 u 0

=> calcul des contraintes sur M1

x 0 -1 1 x 2
y -2 0 0 y 0 x 2
0 y 2
M1 = z + 1 -1 > 1 => z > 2
1 M0 = z > 1
t 0 -1 1 t 2
u 0 2 0 u 0 t 2
u 0
=> calcul de M0
 4.3.2. Formalisation : propriétés
dynamiques
Marquage accessible et graphe de marquage
– Marquages accessibles (ou successeurs)
• Un marquage M' est un marquage accessible (successeur de M) s'il
existe une séquence de transitions s tel que
M —s M'

• L'ensemble des marquages accessibles depuis M est noté A(R,M)

– Graphe des marquages accessibles

• Le graphe des marquages accessibles, noté GA(R,M), est le graphe
ayant comme sommets les marquages de A(R,M) et tel qu'il existe
un arc entre deux sommets M1 et M2 si et seulement si
M1 —t M2
où t est une transition du RdP
 4.3.2. Formalisation : propriétés
dynamiques
Marquage accessible et graphe de marquage
Exemple :
 4.3.2. Formalisation : propriétés
structurelles
Exemple
Graphe de marquage :
Idle1 Idle2
1 (Idle1
0
d1 d2 1 Idle2
f1 f2
Busy1 Res Busy2 0
1 Res)
f1 f2

T= (d1, f1, d2, f2) 0 1

d1 d2
(Busy1) 1 0
Idle1 -1 1 0 0 1 0
Busy1 1 -1 0 0 0 (Busy2) 1
P= Idle2 C= 0 0 -1 1 0 0
Busy2 0 0 1 -1
Res -1 1 -1 1
 4.3.2. Formalisation : propriétés
dynamiques
Marquage accessible et graphe de marquage

Remarque importante : le graphe des marquage peut être infini

=> dans ce cas, le RdP est non borné

Exemple :

(1) —t (2) —t (3) —t (4) —t …

2
t
 4.3.2. Formalisation : propriétés
dynamiques
Propriétés des RdP
– Place et RdP k-bornés
• Une place est dite k-bornée pour un marquage initial si sa marque
ne dépasse jamais k (binaire si k=1)
• Un RdP est k-borné si toutes les places le sont
• C'est une propriété décidable, grâce à la monotonie
– Transition et RdP vivants
• Une transition est dite quasi-vivante pour un marquage M s'il
existe un marquage accessible à partir de M permettant de la
franchir
• Une transition est dite vivante si elle est quasi vivante pour tout
marquage accessible à partir de M0
• Un RdP est dit vivant si toutes ses transitions le sont
– Un RdP ne contient pas de blocage s'il peut
continuellement évoluer
– Un RdP est dit réinitialisable si M0 est accessible à partir
de tout marquage accessible à partir de M0
 4.3.2. Formalisation : propriétés
dynamiques
Propriétés des RdP

– Les propriétés de k-borné, vivacité, blocage… sont

souvent difficile à établir, bien que décidables

– Mais, il existe des méthodes d'analyse

• portant sur le graphe des marquages (pour les réseaux
bornés)
• portant le graphe de couverture (pour les réseaux non
bornés)
• structurelle indépendamment des marquages initiaux
déterminant les propriétés de RdP dans de très nombreux cas
!

=> Arsenal théorique important !!

 4.3.2. Formalisation : propriétés
structurelles
• Idée :
– Déterminer les propriétés d’un RdP à partir de sa structure
indépendamment de son marquage

Notion de composante conservative positive :

Soit un RdP R=(P, T, Pre, Post)
Soit Vp un vecteur de NP
Vp est appelé composante conservatrice positive ssi
VpT . C = 0

=> Une composante conservatrice positive est un ensemble de

place dans lequel le nombre de jeton est borné quelque soit les
transitions franchies
 4.3.2. Formalisation : propriétés
structurelles
Exemple
T= (d1, f1, d2, f2)
Idle1 Idle2
Idle1 -1 1 0 0
Busy1 1 -1 0 0
d1 d2
P= Idle2 C= 0 0 -1 1
Busy1 Res Busy2
Busy2 0 0 1 -1
f1 f2 Res -1 1 -1 1

Composantes conservatrices positives :

1 (Idle1 0 0
1 + Busy1) 0 1 (Busy1

V1= 0 V2= 1 (Idle2 V3= 0

0 1 + Busy2) 1 + Busy2
0 0 1 + Res)
 4.3.2. Formalisation : propriétés
structurelles
Notion de composante conservative positive :

Si une place appartient à une composante

conservatrice postive, alors cette place est k-bornée

Si toutes les places d’un réseau appartiennent à une

composante conservatrice positive, alors le réseau est
k-borné (réciproque fausse)

Le nombre de jetons circulant dans une composante

conservatrice positive est déterminé par le marquage
initial
 4.3.2. Formalisation : propriétés
structurelles
Exemple
Idle1 Idle2

V1 = (Idle1 + Busy1)
d1 d2
V2 = (Idle2 + Busy2)
Busy1 Res Busy2
V3 = (Busy1 + Busy2 + Res)
f1 f2

 Les trois composantes V1, V2 et V3 couvrent l’ensemble du réseau

 Le réseau est k-borné

 Le nombre maximal de jeton dans Busy1 est 1 (marquage initial)

 Le nombre maximal de jeton dans Busy2 est 1 (marquage initial)

 Il ne peut pas y avoir 1 jeton à la fois dans Busy1 et Busy1 car

Busy1 + Busy2 < Busy1 + Busy2 + Res = 1 (marquage initial)
4.4. Exemple : un système de deux
équipements interconnectés
…
 4.4. RdP : exemple d'un système
interconnecté
Description informelle

Bureau
Voisin
Imprimante

Console

=> 2 cas d'utilisation (à la UML)

– cas d'utilisation 1
• on imprime un texte "Imp1" (imprimante)
• on valide l'impression du texte "Val" (console)
– cas d'utilisation 2
• on entre un texte "Edit" (console)
• on imprime le texte "Imp2" (imprimante)
 4.4. RdP : exemple d'un système
interconnecté
=> Diagramme de collaboration à la UML

– cas d'utilisation 1

(1) D.imp1
(2) D.val

imprimante console
(4) F.imp1 (3) F.val
 4.4. RdP : exemple d'un système
interconnecté
=> Diagramme de collaboration à la UML

– cas d'utilisation 2

(1) D.edit
(2) D.imp2
imprimante console
(4) F.edit
(3) F.imp2
 4.4. RdP : exemple d'un système
interconnecté
=> Diagramme de séquence à la UML

– cas d'utilisation 1

imprimante console

D.imp1
Imp1 D.val

Val
F.val
F.imp1
Fin.imp
 4.4. RdP : exemple d'un système
interconnecté
=> Diagramme de séquence à la UML

– cas d'utilisation 2

imprimante console

D.edit
Edit
D.imp2

Imp2
F.imp2

Fin.edit
F.edit
 4.4. RdP : exemple d'un système
interconnecté
=> RdP de l'imprimante et de la console
Idle-imprimante Idle-console

D.imp1 D.imp2 D.edit D.val

Imp1 Imp2
imprimante

Edit Val

D.val F.imp2 D.imp2 F.val

console
Att.val Att.imp2

F.val F.imp2

Fin.imp Fin.edit

F.imp1 F.edit
 4.4. RdP : exemple d'un système interconnecté
Idle-imprimante Idle-console

D.imp1 D.imp2 D.edit D.val

Imp1 Imp2 Edit Val

imprimante

D.val F.imp2 D.imp2 F.val

console
Att.val Att.imp2

F.val F.imp2

Fin.imp Fin.edit

F.imp1 F.edit

=> Communications synchrones

• synchronisation des actions « D.val », « F.val »
• synchronisation des actions « D.imp2 », « F.imp2 »
=> fusion des transitions
 4.4. RdP : exemple d'un système interconnecté
=> Le RdP global
Idle-console
Idle-imprimante

D.edit
D.imp1
Edit
Imp1
D.imp2
D.val
Imp2 Att.imp2
Att.val Val
F.imp2
F.val
Fin.edit
Fin.imp
F.edit
F.imp1

Remarque :
les places Att.val
et Att.imp2 sont
inutiles
4.4. RdP : exemple d'un système interconnecté

=> Le RdP global

Idle-console
Idle-imprimante

D.edit
D.imp1
Edit
Imp1
D.imp2
D.val
Imp2
Val
F.imp2
F.val
Fin.edit
Fin.imp
F.edit
F.imp1
 4.4. RdP : exemple d'un système interconnecté

Analyse :
La séquence
• D.imp1; D.edit;
mène à un bloquage mortel

=> ajout d'un opérateur (sémaphore) pour

empêcher les deux demandes simultanées.
 4.4. RdP : exemple d'un système interconnecté
=> Le RdP global opérateur

Idle-console
Idle-imprimante

D.edit
D.imp1
Edit
Imp1
D.imp2
D.val
Imp2
Val
F.imp2
F.val
Fin.edit
Fin.imp
F.edit
F.imp1

=> plus de blocage

 4.4. RdP : exemple d'un système interconnecté
=> Le RdP global opérateur

Idle-console
Idle-imprimante

D.edit
D.imp1
Edit
Imp1
D.imp2
D.val
Imp2
Val
F.imp2
F.val
Fin.edit
Fin.imp
F.edit
F.imp1

=> à nouveau un blocage possible

 4.4. RdP : exemple d'un système
interconnecté
Commentaires sur l'exemple :
– la présence ou non de blocages mortels peut dépendre
• de la structure du réseau de Petri, c'est-à-dire de celles des
automates et de leurs communications
• mais aussi du marquage initial (nombre d'automates identiques)

– C'est un problème critique

– Prouver l'absence de blocage est un problème difficile

3.5. Raffinement (top-down) et
composition
Ou, comment modéliser un système complexe en
Réseaux de Petri … ?
– Raffinement
– Composition
– Exemple
 3.5. Raffinement et composition de
RdP
Raffinage :
Principe :
– substituer une transition par un bloc "bien formé"
=> on introduit des détails en conservant les
"bonnes" propriétés

=> bloc
 3.5. Raffinement et composition de
RdP
Raffinement :
Blocs bien formés standards :

séquence do-while
if-then-else fork-join
3.5. Raffinement et composition de RdP
Composition asynchrone
Principe : fusion de places
ent1 ent2

a c

p3 p4

p1 p2
b d
3.5. Raffinement et composition de
RdP
Composition synchrone
Principe : fusion de transitions

ent1 ent2

te
a
b
3.5. Raffinement et composition de
RdP
Exemple : un système de transport par chariots filoguidés
Contraintes :
– Un seul chariot par section
– Un seul chariot en mouvement par cellule

5
cellule 2-4
4
1 2

3
 3.5. Raffinement et composition de RdP
Zone de mouvement
(Mvt)
– Une section :
Zone d'attente pour entrer dans
la section suivante
(Porte)

e.s.2 Mvt2 a.p.2 Porte2 s.s.2

(par exemple pour la section 2)

Sec.libre2
 3.5. Raffinement et composition de RdP

– Une section :
contrainte : un seul chariot en mouvement dans la
section 2-4
=> introduction d'une place « espace »
Espace2

e.s.2 Mvt2 a.p.2 Porte2 s.s.2

Sec.libre2
3.5. Raffinement et composition de RdP
– Une section :
contrainte : un seul chariot en mouvement dans la
section 2-4
=> introduction d'une place « espace »
=> fusion des places « Espace » des sections 2 et 4
Sec.libre4

e.s.4 Mvt4 a.p.4 Porte4 s.s.4

Espace
e.s.2 a.p.2 Porte2 s.s.2

Mvt2

Sec.libre2
 3.5. Raffinement et composition de RdP
– Réseau de sections :
contrainte : un seul chariot par section
=> fusion des transitions s.s.1 et e.s.2, s.s.3 et e.s.4, s.s.4
et e.s.5
Sec.libre3 Sec.libre4 Sec.libre5

Mvt4
Mvt3 Porte3 Porte4 Mvt5 Porte5
Espace

Porte1 Mvt2 Porte2

Mvt1

Sec.libre1 Sec.libre2
3.6. Quelques extensions…

– Les réseaux colorés

– Les arcs inhibiteurs
 3.6. Extensions
Motivations des extensions

– Certaines propriétés ne peuvent pas être

exprimées à l'aide des réseaux usuels

– Nécessité de réduire la taille des modélisations

– Besoin d'avoir une information plus précise sur les

jetons transitant dans le réseau
 3.6. Extensions : RdP colorés
Les RdP colorés
– Les jetons sont « typés » par des couleurs.
– Le nombre de couleurs est fini.
– Ces réseaux permettent de représenter de manière
compacte des systèmes ayant des composantes aux
comportements identiques.

=> Différentes couleurs de franchissement associées à

chaque transition
• fonctions associées aux arcs
• couleur : par exemple un n-uplet
• disparition/création de couleurs par le franchissement de
transitions
 3.6. Extensions : RdP colorés
Les RdP colorés
– Exemple
 3.6. Extensions : RdP colorés
Les RdP colorés

– Un rdP coloré n'est qu'une représentation avec un

graphisme condensé d'un rdP ordinaire.

=> Les propriétés d'un rdP coloré sont les mêmes que
celles des rdP ordinaires,
 3.6. Extensions : arc inhibiteurs
Propriété inexprimable : le test à zéro

– Dans le cas général, il est impossible de tester si le contenu

d'une place est vide: autrement dit, il est impossible de
définir un RdP pour lequel une transition est tirable si une
place donnée ne contient pas de jeton.

– Intuitivement, le « test à zero » est en contradiction avec le

principe de monotonie (dans les RdP traditionnels)

– Dans les RdP traditionnels, la valuation à zéro équivaut à

une absence d'arc...
 3.6. Extensions : arc inhibiteurs
Arc inhibiteur
– La transition est tirable si et seulement si la place d'entrée est vide.

=> Pouvoir d'expression très grand

• Les RdP à arcs inhibiteurs ont la même puissance de calcul qu'une machine de
Turing, en particulier grâce au test "si Pr=0 alors aller en Pei sinon aller en Pej"
qui permet de modéliser toute forme de branchement (boucles, tests).
• Une place qui serait place de sortie de toute transition du RdP ne sera bornée
que si l'activité est de durée finie.
• Le bornage d'un RdP à arcs inhibiteurs est donc un problème équivalent à celui
de l'arrêt d'une machine de Turing, donc indécidable (de même que les
propriétés d'accessibilité et de vivacité).
 3.7. Conclusion
• formalisme d'emploi relativement aisé, ayant fort peu d'éléments de
base

• formalisme utilisé dans des domaines très différents

• formalisme ayant un atout indéniable : son « arsenal » théorique

• formalisme orienté modèle - trop « limité » pour représenter finement

un logiciel

=> Exercices en TD n°1.