Cours et TD du 12/10/2023

Comment connaître si un réseau est borné ou non ?

La création de jeton permet de créer un réseau non borné.

Rappel : Soit $N$ places dans le réseau, $p_{1} \dots p_{N}$ est le marquage.

Nombre des marquages possibles dans un réseau de Petri bornée : $(K+1)^{N}$ avec $K$ la borne et $N$ le nombre de marquages.

Pour répondre à la question, voici un exemple :

On a donc :

Si $M_1$ et $M_2$ sont deux marquages :
$$M_{1} \leqslant M_{2} \text{ SSI } \forall p \in P \quad M_{1}(p) \leqslant M_{2}(p)$$
Développer le graphe de marquages :

• On part du marquage initial
• On explore les successeurs
• Traitement d’un successeur $M$ :
  • Si $\exists M'$ un ancêtre de $M$ tant que $M' \leqslant M$ alors remplacer $M$ par $M_{\omega}$ où :
    • $M_{\omega}(p) = \omega$ si $M'(p) < M(p)$
    • $M_{\omega}(p) = M(p)$ si $M'(p) = M(p)$

Rappel sur les transitions et ajout de l’arc inibiteur :

Priorité

Ordre (partiel) sur les transitions :
$$t_{1}< t_{2}$$
$\forall M$, a partir de $M$, $t_{1}$ est exécutable uniquement si $t_{2}$ ne l’est pas (parce que sinon on doit exécuté $t_{2}$ et non $t_{1}$)

Dans ce schéma, on ne veut jamais avoir les deux utilisations en même temps. On peut utiliser des priorités pour éviter ce conflit.

Le conflit est entre $t_{1}$ rendre et $t_{2}$ prendre.

Est-ce que c’est possible de transformer un réseau de Petri avec des arcs inhibiteurs vers un réseau de Petri avec des priorités ? Et inversement ?


Exemple pour les $T$-bornés : est-ce que c’est borné ?