Au plan structurel, alors qu'un graphe de fluence (la modélisation graphique pour machines d'états par prédilection) n'est constitué que de noeuds et d'arcs, on voit apparaitre dans un réseau de Petri deux catégories de noeuds (Figure ci-dessous):

Les noeuds d'un RdP

        -  Les  places               (symbolisées par des cercles)
        -  Les  transitions        (symbolisées par des rectangles)

On dit d'un RdP que c'est un "graphe biparti" voire, plus naturellement, un graphe places-transitions.

Selon les circonstances, et dès lors qu'il n'y a pas d'ambiguités, ou que la complexité de la représentation ne l'impose pas, les transitions peuvent ètre représentées par de simples barres.
 

Les arcs

Places et transitions sont reliées par des arcs. Tout arc devant respecter la règle ci-après:

Un arc ne peut relier qu'une place à une transition ou une transition à une place  (figure).

Poids d'un arc :

A tout arc est associé un poids  n (n pris dans l'ensemble des entiers naturels).  Si ce poids n'est pas rappelé à hauteur de l'arc il sera considéré par défaut comme valant  1.

Réseau ORDINAIRE

         L'arc de poids n = 1  est un arc ordinaire.

Si tous les arcs d'un réseau sont ordinaires le réseau sera dit ORDINAIRE. Les comportements  d'automates seront souvent modélisés par des réseaux ordinaires.
 
On dira d'un réseau de Petri que c'est un quadruplet R.

P est l'ensemble fini de places.
T l'ensemble fini de transitions.
Pre l'ensemble fini des arcs entrants ()
Post l'ensemble fini des arcs sortants ()

Quelques définitions :
 

a) concernant les transitions :

JONCTION
         Deux ou plusieurs arcs aboutissant à une mème transition constituent, avec cette transition, une jonction.

DISTRIBUTION
         Deux ou plusieurs arcs partant d'une mème transition constituent une distribution.
         Jonctions et distributions sont des noeuds ET.

b)   concernant les places:

ATTRIBUTION
         Un ou plusieurs arcs aboutissant à une mème place constituent une attribution (convergence d'arcs sur une mème place ).

SELECTION
         Deux ou plusieurs arcs issus d'une mème place constituent une sélection.
         Attributions et sélections sont des noeuds OU.

TRANSFERT
        Un transfert est une transition ne présentant qu'une place d'entrée et une place de sortie.

        Un transfert pourra ètre considéré comme une jonction suivie d'une distribution. Avec jonction et distribution limitées à un seul arc.

Notations :

         Pour une transition tj, toute place reliée à cette transition par un arc entrant ou un arc arrivant sur  tj est une place d'entrée pour cette transition ( places p3  et  p4   pour t3  sur le réseau       ). L'ensemble des places d'entrée d'une transition  tj  sera notée  :       °tj

         Toute place reliée à  tj  par un arc partant de  tj  est une place de sortie ( p   et   p  pour  t    figure). L'ensemble des places de sortie d'une transition tj  sera notée  :       tj°

         (transitions d'entrée et de sortie d'une place  pi).
 

Marquage  d'un  réseau :

Procéder au marquage d'un réseau R c'est répartir un certain nombre de jetons ou marques dans les places de ce réseau. On dit alors du réseau qu'il est marqué.

    On associe ainsi à chacune des places p du réseau un entier  n (avec  n >= 0). C'est le nombre de marques dans  la place  pi de R.  Ces jetons pourront ètre symbolisés par des points dans les places. On pourra aussi noter directement la valeur  n  dans la place.

On notera  M( pi )  le marquage de la place i ou le nombre de jetons dans  pi.
 

Marquage initial d'un réseau.

A tout réseau  R  on devra associer un marquage initial, donc une répartition préalable de jetons dans les places. C'est le marquage initial du réseau noté:    M0

    Nous verrons par la suite que le marquage initial d'un réseau peut conditionner pour une bonne part les propriétés ou caractéristiques de ce réseau. On accompagnera donc systématiquement tout réseau de son marquage initial, on ne s'en dispense que si il n'y a aucune ambiguité sur le marquage de départ.
 

         Définissons les règles qui permettrons sur la base de "franchissements" de transitions (on dit aussi tirs) de modifier le marquage d'un réseau.

REGLES DE FRANCHISSEMENT DES TRANSITIONS

Validations :

         Un arc  entrant Pi  ---->  Tj   et de poids  n  est dit "validé" si on dénombre une quantité de jetons dans la place Pi au moins égal à  n . Soit si :
                                                                                                    M(pi)  <=   n

         Une transition  tj  est validée ou "franchissable" si tous ses arcs d'arrivée sont individuellement validés. On dit aussi de cette transition qu'elle est "sensibilisée" ou encore susceptible d'ètre "mise à feu" .

Réseau (        ), la transition t₃   est validée, la transition t₁  ne l'est pas (arcs D, t₁ n'est pas validé).
 

Franchissement d'une transition:

         Si une transition t est validée, on peut déclencher une procédure de franchissement de cette transition (tir,  mise à feu). Ce franchissement s'effectue en deux étapes indivisibles.

         1' ) Dans chacune des places d'entrée  pi  de la transition on prélève n  marques si  n est le poids de l'arc pi ---> t.
         2' ) Dans chacune des places de sortie  pj, on dépose m  marques si  m  est le poids de l'arc  t ---> pj.

Illustration :

Réseau (RdP 07), les transitions t3, t4 et t1 sont franchissables. Décidons de franchir t1. Son franchissement s'opére en deux temps .

     - Retrait des jetons dans les places d'entrée
     - Rajout des jetons dans les places de sortie

(Ce conformément aux indications de poids associées aux arcs. Ces deux opérations effectuées en séquence restent indivisibles)

    Sur le réseau précédent, procédons au franchissement de la transition  t1.
amène l'état de marquage  M1  du réseau (       ).

Notation :
                    t1
         M0  ------->  M1  ou encore :            M0   (t1   >   M1        (M0  transition t1  amène M1)

La condition pour qu'une transition  t  soit franchissable s'écrit:

                          M(p)   =>   PRE(p, t)

    qui se généralise à l'ensemble des places d'entrée de la transition   t  sous la forme :

                          M  =>  PRE(t)
 

Représentations matricielles:

Séquence de franchissements:
 

Une suite S  de franchissements dans l'ordre des transitions ti, tj, tk sera notée   S  =  ti,  tj,  tk
On pourra trouver dans une mème séquence de franchissements la répétition d'une mème transition t si cette transition doit ètre franchie plusieurs fois successivement avant franchissement des autres transitions. Une séquence de franchissements peut ètre légale ou pas. Pour le RdP (      ), la séquence  S =  t2, t1, t3, t4  n'est pas légale puisque le franchissement des transitions dans cet ordre est impossible. La transition t3 fait obstacle.
 

Graphe d'états   (G.E)

Un RdP ordinaire constitué uniquement de noeuds OU donc de noeuds qui ne sont que des attributions ou des sélections est un graphe d'état. On ne peut rencontrer dans un RdP à caractéristique de graphe d'états ni jonction ni distribution (RdP sans noeuds ET). Ce graphe s'apparente maintenant à un graphe constitué d'une seule catégorie de noeuds (les places). Les transitions devenant les arcs  interconnectant ces noeuds. C'est cette fois l'équivalent, quant à sa structure, du graphe de FLUENCE.
 

Graphe de transition d'état  (G.T.E)

         Un graphe d'état dont le marquage initial ne fait apparaitre qu'un jeton et un seul est un graphe de transition d'état. Ce graphe ne contiendra plus par la suite, et quelles que pourraient ètre les séquences de franchissements, qu'un seul et mème jeton. On dit alors que le jeton est conservatif. Un tel graphe conduit souvent à la matérialisation d'une machine dite machine d'états (state machine) concue autour d'un registre d'ETAT.
 
 

Arc INHIBITEUR

Un arc inhibiteur ne peut relier qu'une place à une transition. Il se termine (du coté de la transition) par un petit cercle au lieu d'une flèche. Un arc inhibiteur peut ètre de poids n (figure         ) .

Validation d'un arc inhibiteur :

      A l'inverse des arcs utilisés jusqu'ici, un arc inhibiteur de poids  n  est "validé" si la place de départ de l'arc n'a pas n jetons. Et dans le cas particulier du poids unité, si la place d'entrée est vide de toute marque.

Franchissement d'une transition avec arc inhibiteur

Le franchissement  de la transition à laquelle aboutit un arc inhibiteur ne peut se faire que si l'arc inhibiteur est lui mème validé. L'opération de franchissement n'a alors aucune incidence sur le marquage  de  la place de départ de l'arc inhibiteur. Pour un arc inhibiteur de poids '1', la place qui est vide reste vide. On se reportera aux exemples de la figure (       ).

N.B:  L'arc inhibiteur n'est pas reconnu comme un élément faisant explicitement partie des éléments constitutifs  d'un RdP tels que définis à l'origine. Le réseau qui fait apparaitre des arcs inhibiteurs  échappe aux possibilités d'analyses formelles de ses propriétés. Il se trouve par contre qu'à des fins de confort de la visualisation et d'implémentations automatisées, l'utilisation de cet arc s'avère rendre de précieux services.

On peut toujours éviter les arcs inhibiteurs afin de rester dans le cadre strict de la modélisation RdP. On substitue à tout arc inhibiteur la structure équivalente proposée réseau (         ).

Réseau VIVANT

         Un réseau est VIVANT, pour un marquage initial  M0  donné,  si pour toute transition  ti  et quel que soit le marquage  ultèrieur Mk  appartenant à  Q(M0), il existe une séquence légale de franchissements à partir de  Mk  contenant  ti. En d'autres termes, il sera toujours possible de repasser par le franchissement de la transition  ti.
 

Réseau  SAUF

         Pour un marquage initial  M0  donné, un réseau ordinaire est sauf si il est borné à  1. Aucune de ses places n'est susceptible de contenir plus d'un jeton à la fois quel que soit le marquage atteint du réseau.
 

Réseau  CONFORME

         Un réseau est "conforme" si il est  VIVANT  et  SAUF.

Cette propriété sera souvent exigée des modèles de représentation des cahiers des charges des automatismes logiques.
(Exemple de réseau non conforme)

Réseau  PROPRE

         Un réseau est propre pour un marquage initial  M0 si, quel que soit le marquage  Mi appartenant à  Q(M0),  il existe une séquence de franchissements permettant de retrouver le marquage  Mi.

         Le réseau  (     ) emprunté à Valette  ( VAL 1 ) n'est pas propre pour  M0 = (1, 3). Son graphe des marquages conséquents (     ) suffit à le prouver par la présence du marquage (1, 3) qu'on ne peut plus retrouver ultèrieurement.
 

RESEAU  PUR

    Boucle élémentaire :

 Lorsqu'une place est simultanément  place d'entrée et place de sortie pour une mème transition, nous avons à faire à une boucle élémentaire (fig   ).

Un réseau est pur s'il ne fait apparaitre aucune boucle élémentaire. Ou encore si pour toute transition  t  de ce réseau on vérifie:
                                               °t  ^   t°  =   0          (vide)        ^  :  intersection
On pourra toujours représenter un réseau pur par sa matrice d'incidence.

Réseau  Libre choix

Dans un réseau libre choix, tout arc partant d'une place ne peut ètre que:
     - L'unique sortie de cette place
     - Ou l'unique entrée de la transition   (OU inclusif)
 

réseau BORNE

         Pour un marquage initial  M0  donné, une place  p  est bornée si:

              M    Q(M0)        M(p)  <  B      avec  (B appartenant à   N )

         Un réseau est dit borné pour un marquage initial  M0  donné si toutes ses places le sont pour ce marquage initial.

    Pour le marquage initial précisé, le réseau (      ) est borné (B = 1). Le réseau (      ) n'a pas de borne. Il y a en effet accumulation de jetons possible en place (      ).
 

Réseau CONSISTANT

        Un réseau vivant et borné est un réseau consistant.

CONFLIT

On dit qu'il y a partage d'une place  Pi  lorsque cette place est place d'entrée d'arcs aboutissant à des transitions différentes, transitions ètant elle-mèmes des jonctions. La place  Pa  de la figure  (     ) est une place partagée. Cette place introduit un "conflit".

Pour un marquage atteint, si les deux transitions sont franchissables, se pose le problème de déterminer laquelle des deux devra ètre franchie la première? (Rappelons que dans un RdP une opération de franchissement est une opération indivisible).

Il faudra toujours accorder une attention particulière aux cas de conflit.
En présence d'un conflit tout outil de synthèse devra signaler le conflit et demander à ce que celui-ci soit résolu. On peut ètre amené alors, à décider d'une hiérarchie entre les transitions concernées par le conflit et à affecter une priorité  (T1 > T2 ). On s'oblige à procéder au franchissemnt de  T1  d'abord puis à celui de  T2  si cette transition reste encore franchissable après le franchissement de  T1.

Nous verrons plus loin que nous pourrons aussi spécifier des conditions supplémentaires sur les évènements que nous serons amenés à associer aux transitions. Ainsi, dans le cas (     )  l'intersection des événements logiques  u  et   /u . v   étant nul, il ne peut pas y avoir de franchissement simultané.

Nous rencontrerons aussi des conflits au plan structurel du réseau mais ne posant pas de problème si on tient compte du marquage initial et de l'ensemble des marquages atteignables    (fig       ).

Graphe DES MARQUAGES CONSEQUENTS
 

         L'ensemble des marquages atteignables (accessibles) à partir d'un marquage  Mi  sera appelé  classe des marquages conséquents de Mi  et noté :
                                                                               Q( Mi )

     Pour un réseau ordinaire et conforme, on peut  représenter l'ensemble de ces marquages atteints sous forme d'un graphe dit "graphe des marquages conséquents de Mi". Le graphe obtenu a alors les caractéristiques structurelles d'un graphe d'états. Chacun des états de ce nouveau graphe, qui a les caractéristiques cette fois d'un graphe de fluence ordinaire, rend compte d'un état de marquage du réseau en particulier.

N.B:
On ne peut construire le graphe des marquages conséquents d'un réseau que si celui-ci est borné.
 

MACRO-PLACE
 

Dans une conception hiérarchisée, on allège une représentation conprenant un grand nombre de places en en regroupant certaines dans une seule et mème place. C'est une macro-place.

- Dans le cas d'un RdP ordinaire, la délimitation de la collection de places susceptibles de constituer une macro-place devra se faire en s'assurant que de chacune des entrées dans la macroplace on peut atteindre n'importe laquelle des sorties de cette macro-place.

- On entre dans une macro-place par des arcs d'arrivée sur des places. On sort d'une macro-place par des arcs de sortie de places, donc des arcs d'arrivée sur des transitions extérieures à la macro-place. Le découpage en pointillés sur le réseau  (     )  ne saurait constituer une macro-place.

Ce n'est qu'en respectant ces conditions que l'on conserve la possibilité de procéder aux analyses des propriétés du réseau représenté cette fois au niveau macro-places.

Les macro-places participeront pour une part à la modélisation hiérarchisée des graphes de controle. La macro-place représente alors toute une activité qui n'a pas lieu d'ètre détaillée au niveau de représentation ou on se situe.
 

MACRO-TRANSITION

La forme duale de la macro-place est la macro-transition. On peut regrouper un certain nombre de places et de transitions dans une seule et mème macro-transition. L'exemple proposé figure (     ) est emprunté à PETERSON   (Computing surveys, Vol 9, N°3, sep 1987).
 

                                                            BIBLIOGRAPHIE
 

                                                 

poids

  Etablir la séquence de franchissement la plus longue avant blocage du réseau. Est-elle la seule ?