Rețele Petri - studierea proprietăților structurale

Reţelele Petri sunt o reprezentare matematică a sistemelor discrete distribuite. Definite de către Carl Adam Petri în anii 1960 în teza sa de doctorat, reţelele Petri au abilitatea de a generaliza teoria automatelor, prin expresivitatea lor ridicată în domeniul evenimentelor concurente.

O reţea Petri se compune dintr-un tip particular de graf orientat notat N şi o stare iniţială M0, denumită marcaj iniţial.

Graful N al reţelei Petri este orientat, ponderat şi bipartit, constând din două tipuri de noduri, denumite poziţii sau locaţii şi respectiv tranziţii; arcele orientate unesc fie o poziţie cu o tranziţie, fie o tranziţie cu o poziţie.

Definirea proprietăţilor structurale şi criterii de caracterizare

Proprietăţile structurale ale reţelelor Petri netemporizate depind numai de topologia reţelei şi nu depind de marcajul iniţial într-unul din sensurile următoare:

- fie proprietatea se păstrează indiferent de marcajul iniţial;

- fie proprietatea se referă la faptul că există marcaje iniţiale care asigură anumite secvenţe de executări de tranziţii.

Această dependenţă numai de topologie face ca tehnicile de analiză a proprietăţilor structurale să utilizeze instrumente specifice algebrei liniare care exploatează proprietăţile matricei de incidenţă.

În cele ce urmează, Zm(Rm) si Znxm, pentru n,m ∊ N*, reprezintă mulţimea vectorilor coloană cu m elemente numere întregi (reale), respectiv cea a matricelor de dimensiune n x m cu elemente numere întregi. Vectorul cu toate elementele nule se notează cu 0.

Fie x, y ∊ Zm,doi vectori de aceeaşi dimensiune, x = [x1,x2, ,xm]T, y = [y1,y2, ,ym]T în continuare vom utiliza următoarele notaţii de tip inegalitate între vectorii x şi y:

Mărginire structurală

Se spune că o reţea Petri N cu marcajul iniţial M0 este structural mărginită dacă este mărginită (în sens comportamental) pentru orice marcaj iniţial finit. Se spune că o poziţie p a unei reţele Petri este structural nemărginită dacă există un marcaj M0 şi o secvenţă de executări de tranziţii σ pornind din M0 , astfel încât conţinutul în jetoane al poziţiei p să devină nemărginit.

Teorema 1.1. O reţea Petri N este structural mărginită dacă şi numai dacă există un

vector m – dimensional, y > 0 , cu toate elementele numere întregi, astfel încât:

Ay ≤ 0 (1.1)

Teorema 1.2. Într-o reţea Petri N, o poziţie p este structural nemărginită dacă şi numai dacă există un vector n–dimensional x ≥ 0 , cu toate elementele numere întregi, astfel încât:

(1.2.)

Observaţie: Relaţia (1.2) are semnificaţia următoare: elementul vectorului ATx , corespunzător poziţiei p, este pozitiv, celelalte elemente putând fi nule.

Conservativitate

Se spune că o reţea Petri N este conservativă dacă există câte un întreg pozitiv y(p) pentru fiecare poziţie p, astfel încât pentru orice marcaj iniţial M0 fixat şi orice marcaj accesibil din M0, M ∊ R(M0), are loc egalitatea:

(1.3.)

Se spune că o reţea Petri N este parţial conservativă dacă există câte un întreg pozitiv y(p) pentru o parte din poziţiile p (în sensul că nu pentru toate poziţiile), astfel încât pentru orice marcaj iniţial M0 fixat şi orice marcaj M ∊ R(M0), are loc egalitatea.