Reele Petri

BREVIAR Definiie: Reelele Petri (RP) sunt grafuri orientate cu dou tipuri de noduri:

poziii i tranziii. Formal, o RP ordinar i autonom poate fi definit printr-un cvintuplu:

( )RP P T I O M= , , , , 0 unde:

P este mulimea poziiilor, simbolizate prin cercuri; poziiile modeleaz variabile de stare sau condiii;

T este mulimea tranziiilor, simbolizate prin bare sau dreptunghiuri; tranziiile modeleaz evenimente sau aciuni.

Mulimile P i T sunt disjuncte P T = { }I PxT: , 0 1 reprezint arcele care duc de la poziii la tranziii i se mai

numete i funcie de intrare sau IN;

{ }O PxT: , 0 1 reprezint arcele care duc de la tranziii la poziii i se mai numete i funcie de ieire sau OUT.

ntr-o RP, ntotdeauna un arc unete dou noduri de tipuri diferite (o poziie si o tranziie).

M P N: este vectorul de marcaj, definit pe mulimea poziiilor reelei, cu valori n mulimea numerelor naturale; un element m(Pi) al vectorului indic numrul de jetoane de marcaj din poziia Pi a reelei la un moment dat.

Dac se consider poziiile reelei ca variabile de stare ale sistemului astfel modelat, atunci marcajul (vectorul de marcaj) reprezint starea sistemului.

M0 este marcajul iniial la lansarea sistemului (starea iniial). Starea unei RP se modific prin execuia tranziiilor.

Reguli pentru execuia tranziiilor: 1. O tranziie se execut numai dac este valid. O tranziie Tj este valid numai

dac toate poziiile sale de intrare (adic toate poziiile Pi pentru care I(Pi,Tj)=1) sunt marcate (m(Pi)1).

2. ntr-o RP ordinar autonom se execut o singur tranziie la un moment dat (indiferent cte tranziii sunt valide). Aceast regul are la baz dou ipoteze:

a. Dou evenimente independente nu pot s aib loc simultan, b. Fiecare tranziie reprezint un eveniment distinct.

3. Execuia unei tranziii Tj se face n doi pai: a. Din fiecare poziie de intrare a lui Tj se retrage cte un jeton de marcaj, b. n fiecare poziie de ieire a lui Tj se pune un jeton de marcaj.

4. Execuia unei tranziii are durat nul. Din punctul de vedere al nivelelor de reprezentare SED, exist urmtoarele clase

de RP: - reele Petri autonome la nivel logic, - reele Petri temporizate, sincronizate i interpretate la nivel temporal

(determinist), - reele Petri stochastice la nivel stochastic. n afar de aceste clase distincte, a cror putere de modelare este diferit n funcie

de modul de integrare al timpului n model, exist o serie de extensii ale modelelor RP, extensii care se pot aplica fiecrei clase, fr a le modifica nici proprietile i nici puterea de modelare. Rolul extensiilor este de a realiza modele mai compacte.

Dintre acestea, cele mai cunoscute sunt: RP generalizate: se asociaz ponderi (numere naturale) arcelor. n mod

implicit ponderea unui arc este 1. Se mai numesc i RP cu arce ponderate. I: PxT N i O: PxT N

Pentru aceast clas de reele regulile de execuie a tranziiilor se modific astfel:

- dac arcul Pi Tj are ponderea q , Tj este valid dac Pi conine cel puin q jetoane.

- prin executarea lui Tj se retrag q jetoane din Pi ; - dac arcul Tj Pk are ponderea m, prin executarea lui Tj se adaug m

jetoane n poziia Pk. RP cu capaciti: se asociaz capaciti (numere naturale) poziiilor. n mod

implicit, capacitatea unei poziii este infinit. Regulile de execuie ale tranziiilor se modific astfel: o tranziie este executabil dac i numai dac prin execuia ei nu se depete capacitatea vreuneia dintre poziiile sale de ieire.

Tranziii speciale: tranziie surs este o tranziie care nu are nici o poziie de intrare. O astfel de

tranziie este n permanen valid; tranziie capcan (trap) este o tranziie care nu are nici o poziie de ieire. Notaii:

*M = mulimea marcajelor accesibile plecnd de la marcajul M;

S = secven de execuie = succesiune de tranziii ce se pot executa n aceast ordine; M0(S M2: executarea secvenei S pornind de la marcajul M0 conduce la marcajul

M2.

Marcaj superior: M1 M2 m1 (Pi ) m2 (Pi ), Pi ; Marcaj strict superior: M1 > M2 M1 M2 i Pi a.. m1 (Pi ) > m2 (Pi ).