Chapitre 3

Les Réseaux de Pétri

Introduction

Un réseau de Petri est un modèle mathématique servant à représenter divers systèmes

crée en 1962 par Carl Adam Petri. Les Réseaux de Petri sont un outil de modélisation
universellement connu et reconnu pour les possibilités d’analyse, de validation et de
vérification dont ils font preuve. Ils offrent une structure très simple et forment le support de
nombreuses études théoriques des systèmes concurrents; ils permettent de représenter les
concepts de parallélisme et de synchronisation.

Cet outil de modélisation est particulièrement bien adapté à la représentation des

systèmes dynamiques et discrets. Il se prête en effet à une construction modulaire et permet,
dans la globalité du modèle obtenu, de repérer tous les sous-ensembles. Ses propriétés
mathématiques permettent un suivi de la conservation ou de la non conservation des
propriétés individuelles de chaque sous-ensemble.

Les réseaux de Petri permettent aussi la vérification de propriétés aussi bien

structurelles que comportementales. Un grand nombre de propriétés peuvent être exprimés à
l'aide des réseaux de Petri telles que l'absence de blocage et la disponibilité permanente des
fonctionnalités du système.

1. Définitions

Un Réseau de Petri (RdP) est une structure graphique comportant:

• un ensemble de places
• un ensemble de transitions
• un ensemble d’arcs orientés qui associent les places (d’entrée) aux transitions et les
transitions aux places (de sortie) éventuellement porteurs de poids. Ces arcs sont des
liens entre place et transition ou entre transition et place exclusivement.

Dans cette structure se déplacent des jetons (ou marques) qui apparaissent dans les
places et sont susceptibles de franchir les transitions selon certains critères de franchissement.
L’état d’un réseau est défini par son marquage. Un marquage associe à chaque place un
nombre entier positif, que l’on représente graphiquement par des jetons .
 Fig. 01. Exemples de Réseaux de Petri

1.1. Définition formelle

Un RdP est un quadruplet Q = <P, T, Pré, Post > tel que :

• P = {Pi}, i ∈{1,...,n} est appelé ensemble de places
• T = {Tj}, j ∈{1,...,m} est appelé ensemble de transitions avec P∩T = ∅
• Pré est une application de P X T→ N dite fonction de précondition ou d'incidence avant.
• Post est une application de P X T→ N dite fonction de postcondition ou d'incidence arrière.
• Pré (Pi,Tj) est appelé poids de l'arc reliant Pi et Tj.
• Post (Pi,Tj) est appelé poids de l'arc reliant Tj et Pi .

Les places sont représentés par un cercle et les transitions en général par un trait. Le
réseau de Petri est représenté par un graphe avec deux types de sommets les places et les
transitions. Ces différents sommets sont reliés entre eux par des arcs qui joignent des palces à
des transitions (les préconditions) et des transitions aux places (les postconditions). Il convient
aussi qu'un arc possède un poids supérieur ou égale 1 (par défault 1).

1.2. Marquage
On appelle marquage d'un réseau de Petri N = (P, T, Pré, Post) la fonction M: P → N
où chaque place contient un nombre entier (positif ou nul) de marques ou jetons. Le nombre
de marques ou de jetons contenu dans une place Pi sera noté m(Pi). Le marquage du réseau à
l'instant i, M est défini par le vecteur de ces marquages M = (m(P1), m(P2), …,m(Pn)). Le
marquage dit initial décrit l'état initial du système modélisé (M0).
Exemple:

Ce réseau de Petri possède 4 places, 4 transitions et 8 arcs orientés.

Soit donc : P = {P1, P2, P3, P4} et T={T1, T2, T3, T4} ;
Le marquage initial est M0 = (2,1,1,0) ;

1.3. Franchissabilité d'une transition

Soit un réseau de Petri N, une transition Ti de N est franchissable, sensibilisée, tirable
ou déclenchable pour un marquage M si et seulement si toutes les places immédiatement en
amont (les places d'entrée) à cette transition Ti possèdent au moins le nombre de marques
correspondant au poids des arcs reliant respectivement chacune de ces places à cette transition
(∀ p∈P, m(p) ≥ Pre (p, Ti)).

1.3 Le franchissement ou le déclenchement d'une transition

Toute transition sensibilisée par un marquage M est immédiatement franchie. Le
déclenchement de cette transition consomme des jetons de ces places d'entrée et ajoute des
jetons dans chacune des places immédiatement en avales (places de sorties). Le nombre de
jetons consommés et produits correspond aux poids des arcs. Le déclenchement d'une
transition conduit à un nouveau marquage M' défini, pour tout p, par:
M'(p) = M(p) - Pre(p, Ti) + Post(p, Ti)

Le franchissement de la transition Ti est noté par : [ > ′

Exemple:

Avant franchissement Après franchissement

Les marquages sont les suivants :
Avant franchissement : m(P1) = 3 ; m(P2) = 4 ; m(P3) = 1 ; m(P4) = 0 donc M(3, 4, 1, 0)
(3, 4, 1, 0) - Pre(P1, T) - Pre(P2, T) + Post(P3, T) + Post(P4, T) = M'(1, 3, 2, 3)
Après franchissement : m(P1) = 1 ; m(P2) = 3 ; m(P3) = 2 ; m(P4) = 3 donc M'(1, 3, 2, 3)

(3, 4, 1, 0) → ′(1, 3, 2, 3)
Remarques :
1) Le franchissement d'une transition ne garantit pas la conservation de la quantité de marques
globale. Dans l’exemple précédent, on a globalement un jeton de plus après franchissement de
la transition.
Selon les poids attribués aux arcs liés à une transition donnée, les transitions sont :
"Consommatrice", "Génératrice" ou "Conservatrice" de marques.
Soit une transition T reliée à un ensemble de places par n arcs amont (entrants) et m arcs aval
(sortants). Soit Pré(i) le poids d'un arc amont i de la transition T. Soit Post(j) le poids d'un arc
aval j de la transition T.
si ∑ !" Pré(i) < ∑'!" Post(j) alors la transition est génératrice
si ∑ !" Pré(i) > ∑'!" Post(j) alors la transition est consommatrice
si ∑ !" Pré(i) = ∑'!" Post(j) alors la transition est conservatrice
2) Le temps de franchissement d'une transition est nul d'un point de vue purement théorique et
en dehors de toute réalité physique.
3) Dans le principe initial des RdP, rien n'interdit le franchissement simultané de deux
transitions du même réseau. Or, la simultanéité de deux événements n'est pas cohérente pour
le physicien.
4) Les protocoles de franchissement et les conditions de déclenchement décrites
précédemment ne prennent pas en compte la notion de temps. En effet, on fait évoluer le
marquage d'un RdP sans prendre en compte ni la chronologie ni la durée des événements. Il
est donc indispensable, pour l’application, de fixer un certain nombre de règles. Ces règles
sont issues des contraintes temporelles imposées par les systèmes physiques. Elles sont issues
des deux considérations suivantes :
• Tout événement a une durée non nulle.
• Deux événements indépendants ne peuvent être simultanés.
L’évolution du marquage dans un RdP, peut alors dépendre du temps de séjour dans une place
ou du temps de franchissement d’une transition donnés.

1.4. Séquence de franchissement et ensemble de marquage accessibles

1) Une séquence de franchissement à partir d'un marquage M0 est représentée par la suite des
transitions δ= t1, t2, t3, . . . tn telles que le franchissement de chacune d'elles conduit à un
marquage qui sensibilise la suivante :
12 13 16 12 13 18 16
0 → 1 1 → 2 , ..., n-1 → n ou 0 → 1 → 2 → . . .→ n 0 → n
δ
, noté par
2) Un marquage M est dit accessible s'il existe une séquence de franchissement δ tel que:

0 →
δ

3) L'ensemble des marquages accessibles à partir du marquage M0 est noté par *M0

Exemple:
On considère le RdP de l'exemple ci-dessous.
Le marquage initial est M0=(1, 0, 0, 0, 0). Pour ce marquage M0, seule la transition T1 est
validée et son franchissement conduit au marquage M1=(0, 1, 1, 0, 0). On notera ceci :

M0 → M1
2

Pour M1, il y a deux transitions validées T2 et T3. On aura donc :

M1 → M2 = (0, 0, 1, 1, 0) M1 → M3 = (0, 1, 0, 0, 1)
3 8
et
Pour M2, seule la transition T3 est validée, son franchissement conduit à M4 :

M2 → M4 = (0, 0, 0, 1, 1)
8

Pour M3, seule la transition T2 est validée, son franchissement conduit à M4 :

M3 → M4 = (0, 0, 0, 1, 1)
3

Pour M4, seule la transition T4 est validée, son franchissement conduit à M0 :

M4 → M0 = (1, 0, 0, 0, 0)
:

Le franchissement, à partir de M0, de t1 puis t2 conduit au marquage M2. T1, T2 est unes
2, 3
0 2 0 → 2
δ
séquence de franchissement noté : ou encore avec δ= T1, T2

Pour l'exemple, la séquence δ= T1, T2, T3 est applicable à partir de M0 et conduit au

δ! 2 , 3 ,
= (1, 0, 0, 0, 0) =(0, 0, 0, 1, 1) donc M4 est accessible.
8
marquage M4. 0 4

L'ensemble des marquages accessible est: *M0 = ={M0, M1, M2, M3, M4}
2. Graphe des marquages ou Graphe de transitions (ou encore Graphe d'états)
Le graphe de marquage accessibles G(N, M0) est défini comme étant le graphe dont les
sommets correspondent aux marquages accessibles à partir du marquage initial M0 et chaque
arc étiqueté par t reliant deux sommets M et M' correspond à une transition franchissable tel
1
que → ′. C'est une représentation graphique des possibilités d'évolution du RdP. Elle est
obtenue en partant du marquage initial et pour chaque nouveau marquage obtenu Mi après le
franchissement d’une transition Tj examiner les différentes possibilités d’évolution du RdP.
Ceci correspond aux différentes transitions validées par le marquage Mi.

Exemple: Pour le RdP précédent, nous obtenons le graphe suivant :

Remarque :
Le graphe peut être fini ou infini. Dans le cas ou il est fini, il sera complet lorsque toutes les
possibilités sont représentées.
Exemple:
3. Arbre de couverture et Graphe de couverture
3.1. Arbre de couverture
L'inconvénient de la méthode précédente est que tous les réseaux n'ont pas un graphe
des marquages accessibles fini. Une méthode alternative est donc proposé. Cette méthode
consiste à construire un arbre de couverture dont le mécanisme de construction est le même
que pour le graphe des marquages accessibles. A ceci prêt que pour chaque nouveau
marquage (nœud du graphe) ajouté, on vérifie s'il n'est pas supérieur à un marquage déjà
présent sur au moins une séquence entre M0 et le nouveau marquage. Si tel est le cas tous les
marquages de place supérieurs sont remplacés par ω. Ce symbole matérialise le fait que la
place en question peut contenir autant de jetons que souhaité (elle est donc non bornée).

Définition: On dit qu'un marquage M est supérieur à un marquage M' (ou couvre un autre
marquage) si et seulement si : ; > ; <=> ∀? ; (?) ≥ ;(?)

Soit N=(R, M0) un Rdp marqué, l’arbre de couverture est construit itérativement de la manière
suivante:
1. M0 correspond à la racine de l'arbre.
2. Construire les successeurs pour chaque transition franchissable à partir de M0. Si un des
nouveaux marquage M' est strictement supérieur à M0, on remplace chacune des composantes
M'(p) supérieures aux composantes correspondantes de M0 par ω.
Pour toute transition t faire Si M0 [t> M' alors insérer M' dans l'arbre;
Si M'> M0 alors pour tout p tel que M'(p)> M0 (p) faire M'(p)= ω Fsi;
3. Pour chaque nouveau marquage Mi de l'arbre faire:
(i) S'il existe sur le chemin de M0 à Mi un marquage Mj = Mi (un marquage ancêtre est
déjà construit), alors Mi n'a pas de successeurs (on arrête la branche).
Si ∃ Mj, (M0 [δ
δ'> Mj [δ
δ''> Mi ) et (Mj = Mi) alors Mi n'a pas de successeurs Fsi;
(ii) Sinon on prolonge l'arbre en ajoutant tous les successeurs de Mi. Pour chaque
successeur Mk de Mi faire:
(a) une composante ω de Mi reste une composante ω de Mk.(ω+n =ω; ω-n=ω)
(b) S'il existe sur le chemin de M0 à Mk un marquage Mj tel que Mk > Mj alors on
remplace chacune des composantes de Mk supérieures aux composantes de Mj
par ω.
Sinon Pour toute transition t faire
Si Mi [t> Mk alors ∀p, Si Mk(p)≠ ω alors Mk(p)= Mi(p) + C(p,t) Fsi Fsi;
Si ∃ Mj , (M0 [δ
δ'> Mj [δ
δ''> Mk ) et (Mk > Mj) alors
pour tout p tel que Mk(p)> Mj(p) faire Mk(p) = ω;
insérer Mk successeur de Mi dans l'arbre;
Fsi;

3.2. Graphe de couverture

Le graphe de couverture d'un réseau de Petri marqué (R, M0) est un système de
transition <Q, ∆, λ, q0) tel que:
Q: un ensemble de marquages sur N∪{ω}, avec ∀k≠0, ω+k =ω; ω-k=ω, ω>k)
∆: l'ensemble des arcs reliant deux éléments de Q par le franchissement d'une transition de R
λ: étiquette les arcs du graphe par le nom de la transition
q0: égale à M0
Le graphe de couverture est obtenu de l'arbre de couverture en fusionnant les sommets
étiquetés par les mêmes éléments (marquages) et redirigeant les arcs entre les sommets ainsi
obtenus.
Exemples: Construire l'arbre et le graphe de couverture des Rdp suivants:
M0 = (1,0) L'arbre de couverture
12
M0 M1 avec M1=(1, 1) M0 = (1,0)

M1 > M0 donc il couvre M0 t1

M1=(1, ω)
13
M1 M2 avec M2=(2, ω) M1 = (1, ω)

M2 > M1 donc il couvre M1

t2
Le Graphe de M2=(ω, ω)
12
M2 M3 avec M3=(ω, ω)
couverture
M2 = (ω, ω)
M0 = (1,0)
∃M2, (M0[{t1, t2}>M2 [t1>M3) et t2
t1
t1 (M2=M3) alors M3 n'a pas de successeurs
13
M2 M4 avec M4=(ω, ω) M3 = (ω, ω) M4 = (ω, ω)
M1 = (1, ω)
∃M2, (M0[{t1, t2}>M2 [t2>M4) et
t2 (M2=M4) alors M4 n'a pas de successeurs

M2 = (ω, ω)
t1,t2
3.3. Propriétés

1. Le graphe de couverture est fini.

2. Le réseau est borné si le graphe de couverture ne contient pas de nœud dont une
composante (au moins) a la valeur ω . Dans ce cas, le graphe de couverture est identique au
graphe d’accessibilité.
3. Le symbole ω introduit une perte d’information
4. D’une manière générale, le graphe de couverture ne permet pas de répondre à des
questions sur :
– L’accessibilité d’un marquage
– La vivacité du réseau
Nb: Dans le cas d’un réseau borné, un marquage M est accessible si et seulement si le graphe
des marquages accessibles contient un nœud représentant M. Dans le cas d’un réseau non-
borné, il est impossible de vérifier à l’aide d’un graphe de couverture si M est accessible. On
peut seulement vérifier qu’il existe un marquage M’ tel que M ⊆ M’.
5. Des réseaux ayant des comportements différents peuvent avoir le même graphe de
couverture

4. Matrices d'incidences
Le réseau de Petri peut être décrit d'une manière algébrique. La matrice d’incidence fait la
synthèse de tous les liens entre places et transitions du RdP. Cette matrice possède un nombre
de colonnes égal au nombre de transitions du réseau, ainsi qu’un nombre de lignes égal au
nombre de places du réseau. Chaque élément de la matrice témoigne de la présence ou de
l’absence de lien entre chaque place et chaque transition, ainsi que du poids attaché à l’arc en
question. La direction l'arc permet de décrire une matrice d'incidence avant et une matrice
d'incidence arrière.

4.1 Matrice d'incidence Avant

La fonction Pré est définie par une matrice d'incidence avant nxm tel que:
ABé(1,1) … ABé(1, G) … ABé(1, I)
E N
⋮ ⋮ ⋮
D M
ABé = D ABé(J, 1) … ABé (J, G) … ABé(J, I) M
D ⋮ M
Pré (i, j) = Pré (Pi,Tj)

CABé(K, 1) … ABé(K, J) … ABé(K, I)L

4.2 Matrice d'incidence Arrière
La fonction Post est définie par une matrice d'incidence arrière nxm tel que:
A OP(1,1) … A OP(1, G) … A OP(1, I)
E N
⋮ ⋮ ⋮
D M
A OP = D A OP(J, 1) … A OP (J, G) … A OP(J, I) M
D ⋮ M
Post (i, j) = Post (Pi,Tj)

CA OP(K, 1) … A OP(K, J) … A OP(K, I)L

4.3 Matrice d'incidence

La matrice d'incidence d'un réseau de Petri est calculé comme suit:
C = Post - Pré avec C(i, j) = Post(i, j) - Pré(i,j)

4.4. Equation fondamentale

Pour une séquence de franchissement δ réalisable à partir d'un marquage Mi, le vecteur
caractéristique S est le vecteur de dimension m (m= nombre de transitions du RdP), défini
comme suit: S(i) = nombre de francissement de la transition Ti dans la séquence δ.
La connaissance de la matrice d'incidence C, du vecteur caractéristique S pour une
séquence de franchissement δ, réalisable à partit d'un marquage Mi, permet de déterminer le
marquage atteignable Mj à l'aide de l'équation suivante:
Mj = Mi + C.S
Cette représentation mathématique permet de suivre l'évolution du marquage du RdP.
Grâce à cet outil, la prédiction de l'état d'un système est possible.

Exemple 01:
 1 0 0 0 1 0 −1 1 0
ABé = Q0 1 1R A OP = Q1 0 1R donc S = Q 1 −1 0 R
0 0 1 0 1 0 0 1 −1
0 1 0 0 0 1 0 −1 1
Pour la séquence de transition δ = <t1, t2, t1> réalisable à partir de M0=(1,0,0,1), le vecteur
caractéristique est S = (2, 1, 0) on atteint le marquage M' comme suit:
1 −1 1 0 0
2
= 0 1 −1 0 Q1R
U + S X X = Q0R + Q 0 1 −1
R X Y1Z =
1
0
1 0 −1 1 0

Exemple 02:

1 0 0 1 −1 1
ABé = Y0 1Z A OP = Y1 0Z donc S = Y 1 −1Z
1 0 0 1 −1 1
Pour la séquence de transition δ = <t1, t2, t1> réalisable à partir de M0=(1,0,1), le vecteur
caractéristique est S = (2, 1) on atteint le marquage M' comme suit:
1 −1 1 0
2
= U + S X X = Y0 Z + Y 1 −1Z X [ \ = Y1Z
1
1 −1 1 0

5. propriétés et caractérisation des réseaux de Petri

Etant donné un réseau de Petri R= (P, T, Pré, Post) et un marquage initial M0.

5.1. Bornitude du réseau

Un RdP est dit borné si le nombre de marques de toutes ses places a une limite finie. Il s'agit
d'exprimer le fait que le nombre de marquages accessibles (le nombre d'états que peut prendre
le système) est fini.
 Une place Pi∈P du réseau est k bornée si et seulement si pour tout marquage M
accessible depuis M0, M(Pi) ≤ k. Dans le cas contraire, la place est dite non bornée.
∀ M∈*M0, ∃ k∈N tel que M(Pi)≤ k
Un réseau de Petri R est dit borné pour un marquage initial M0 si toutes les places sont
bornées. Autrement dit quel que soit le marquage accessible M et quelle que soit la place Pi
considérée, le nombre de jetons contenus dans cette place est inférieur à une borne k.

Remarques :
La bornitude est une propriété dépendant du marquage initial. Pour un RdP borné, on
dira également que le nombre d'états accessibles à partir de l'état initial est fini, le graphe
d'états équivalent peut donc être construit. Lorsque la borne est égale à 1, le RdP est dit Sauf
ou binaire.

5.2. Vivacité du réseau

a- Transition vivante : Une transition Tj ∈T est vivante pour un marquage initial M0 si pour
tout marquage accessible Mi ∈*M0, il existe une séquence de franchissement δ qui contient la
transition Tj, à partir de Mi. Autrement dit quelque soit l'évolution, il subsistera toujours une
possibilité de franchir Tj à nouveau.

b- Réseau de Petri vivant

Un RdP est vivant pour un marquage initial M0 si et seulement toutes ses transition sont
vivantes pour M0 (∀Tj ∈T, Tj est vivante). Un RdP sauf et vivant est dit Conforme. Autrement
dit; à partir du marquage initial, toutes les transitions du réseau sont toujours franchissables,
quelle que soit l'évolution du système.

5.3. Etat de blocage

Un état Mi∈*M0 est un état de blocage (état puit) si et seulement si aucune transition n'est
franchissable. Un blocage est un marquage tel qu'aucune transition n'est validée. Un RdP est
dit donc sans blocage (pseudo vivant) pour un marquage initial M0 si aucun marquage
accessible Mi n'est un blocage.
5.4. RdP propre (Réinitialisable)
Un RdP est propre si pour tout marquage Mi∈*M0 accessible à partir du marquage initial, il
existe une séquence S de franchissement qui ramène au marquage initial:

∀ Mi∈*M0 , ∃δ tel que ]i ]0

δ

Exemples:

Parmi les RdP suivants, déterminer ceux qui sont bornés et ceux qui ne le sont pas.
Sur le 1er RdP les transitions T2 et T3 sont vivantes alors que T1 ne l'est pas. En effet, elle est
franchissable uniquement au démarrage. Le RdP n'est pas vivant.
Le 2ème RdP est vivant, en effet les transitions T1 et T2 sont toujours validées successivement.

Le franchissement de T1 suivi de celui de T3 conduit à une situation de blocage. Cet RdP est
donc avec blocage.

Déterminer si les RdP en question sont propre ou non.

6. Réseau de Pétri Colorés
La modélisation d'un système réel peur mener à des réseaux de Petri de taille trop
importante rendant leur manipulation et/ou leur analyse difficile. Lorsque les modèles
deviennent ainsi volumineux ou complexes et qu'ils contiennent des sous-modèles présentant
des similarités structurelles, il devient intéressant de modifier (étendre) la modélisation par
RdP de façon à obtenir des modèles de plus petite taille en utilisant le principe de coloration.
Les réseaux de Petri colorés (RdPC) offrent une possibilité d'expression plus compacte que
les RdP ordinaires. Ils sont importants pour la modélisation de systèmes de production et sont
très utilisés dans le domaine de l’informatique.
Dans les RdPC, des couleurs, des entiers ou encore un ensemble d'étiquettes sont
associés aux jetons afin de les différencier. Une place peut contenir un ensemble de jetons de
différents couleurs, et une transition peut être franchie de différentes manières suivant la
couleur sélectionnée. Ceci est réalisé en attachant un domaine de couleur à chaque place et
chaque transition.
Dans un RdP coloré les arcs ne seront plus étiquetés par des entiers mais par des
fonctions de couleurs, qui désigneront les actions à effectuer à chaque franchissement. A
chaque arc correspond une fonction qui à chaque couleur de transition associe un vecteur
ligne d'entiers positifs qui décrit de jetons de chaque couleur qui seront retirés ou produits à
chaque franchissement.

Exemple:
L’exemple ci-dessous va permettre de présenter une première approche de la
démarche de coloration. Il s’agit de modéliser l’état de trois machines similaires traitant tour à
tour deux types de pièces C1 et C2. La première modélisation se base sur l’utilisation de
réseaux de Petri ordinaires. Ce RdP se présente sous la forme de trois boucles similaires et
totalement indépendantes. Le marquage initial indique que les machines 1 et 2 sont entrain de
traiter une pièce de type 1, alors que la machine 3 traite une pièce de type 2.

P1 P1 P1

P2 P2 P2

Machine 1 Machine 2 Machine 3

Le même exemple modélisé par un réseau de Petri coloré est présenté ci-dessous. Dans ce
nouveau type de réseau de Petri, les jetons sont dits colorés de par le fait qu’ils ont maintenant
chacun une identité propre. Chaque jeton de ce modèle représente à présent une machine
spécifique. Les deux premières machines, symbolisés par les couleurs <1 rouge> et <2 bleu>,
sont entrain de traiter des pièces de type C1 . La machine 3 traite une pièce de type C2 . Les
jetons <1 rouge>, <2 bleu> et <3 vert> sont alors respectivement situés dans les places P1, P1
et P2.
Les transitions représentent, pour chaque machine le passage d'un type d'usinage à l'autre. Ces
franchissements sont indépendants pour chaque couleur. Le RdPC est plus synthétique.

1 2

3 P2

Réseau de Pétri Coloré

Définition: un multi-ensemble sur un ensemble fini non vide S est une application de S dans
N.
Un multi-ensemble est un ensemble pouvant contenir plusieurs occurences d'un même
élément. Un multi-ensemble µ est noté par:
µ = ∑_∈a ^(_). _ où µ(x) ≥0 désigne le nombre d'occurences de x dans µ
Bag(S) désigne l'ensemble des multi-ensembles sur S.

Exemple:
1) B={a, b, c, d, e}, µ={a, a, b, b, b, d, d} est un multi-ensemble de B tel que:
µ= 2a + 3b + 2d avec µ(a)= 2, µ(b)= 3, µ(c)= 0, µ(d)= 2, µ(e)= 0,
2) m = 2.α + 3.β désigne le multi ensemble m = {α, α, β, β, β} sur l'ensemble S={α ,β}
6.1. Définition formelle d'un RdPC

Un réseau de Petri coloré est tuplet Q = <P, T, C, Pré, Post > tel que :
• P est un ensemble non vide et fini de places
• T est un ensemble non vide et fini disjoint de P de transitions (P∩T = ∅)
• C définit pour chaque place et chaque transition son domaine de couleur
• Pré (respectivement Post) est une fonction linéaire qui associe à chaque p∈P et chaque t∈T
une application de Bag(C(t)) dans Bag(C(p))
• M0 est le marquage initial du réseau; c'est un vecteur indexé par P et M0(p) est un élément de
Bag (C(p)).

6.2. Franchissement d'une transition dans RdPC

a) Une transition t est dite franchissable pour un marquage M et une couleur c∈C(t) si:
∀p∈P , M(p) ≥ Pré(p, t)(c)

b) Le franchisseemnt d'une transition t par rapport à la couleur c pour un marquage M

engendre le nouveau marquage M' défini par:
1,b
∀p∈P, M'(p) =M(p) + Post(p, t)(c) - Pré(p, t)(c) et il est noté: M0 [t, c> M' où 0 ′