Plasa Petri

Rețeaua Petri  este un obiect matematic folosit pentru modelarea sistemelor discrete dinamice, propus de Carl Petri în 1962 .

Este definit ca un multigraf orientat bipartit , format din două tipuri de vârfuri - poziții și tranziții, conectate prin arce. Vârfurile de același tip nu pot fi conectate direct. Pozițiile pot conține etichete (marcatoare) care se pot deplasa în rețea. Un eveniment este declanșarea unei tranziții, în care etichetele din pozițiile de intrare ale acestei tranziții sunt mutate în pozițiile de ieșire. Evenimentele au loc instantaneu sau în momente diferite, în anumite condiții.

Rețeaua Petri este un multigraf, deoarece permite existența mai multor arce de la un vârf al graficului la altul. Deoarece arcele sunt direcționate, acesta este un multigraf direcționat. Varfurile graficului pot fi impartite in doua multimi (pozitii si tranzitii) in asa fel incat fiecare arc sa fie directionat de la un element al unei multimi (pozitii sau tranzitii) catre un element al altei multimi (tranzitii sau pozitii); prin urmare, un astfel de graf este un multigraf direcționat bipartit.

Dezvoltat inițial pentru modelarea sistemelor cu componente care interacționează paralel; Petri a formulat principalele prevederi ale teoriei comunicării componentelor asincrone ale unui sistem de calcul în teza sa de doctorat „Comunicarea automatelor” [1] .

Dinamica

Procesul de funcționare a rețelei Petri poate fi reprezentat vizual printr-un grafic al marcajelor accesibile. Starea rețelei este determinată în mod unic de marcarea acesteia - distribuția cipurilor după poziție. Vârfurile graficului sunt marcaje admisibile ale rețelei Petri, arcele sunt marcate cu simbolul de tranziție declanșat. Se construiește un arc pentru fiecare tranziție excitată. Construcția se oprește atunci când obținem marcaje în care nicio tranziție nu este excitată sau marcaje conținute în grafic. Rețineți că graficul marcajelor accesibile este un automat.

Tipuri de rețele Petri

Unele tipuri de rețele Petri:

Analiza rețelelor Petri

Principalele proprietăți ale unei rețele Petri sunt:

Studiul acestor proprietăți se bazează pe analiza accesibilității. Metodele de analiză a proprietăților rețelelor Petri se bazează pe utilizarea graficelor de marcaje accesibile (acoperire), rezolvarea ecuației stărilor rețelei și calcularea invarianților liniari de poziții și tranziții. Metodele auxiliare de reducere sunt, de asemenea, folosite pentru a reduce dimensiunea rețelei Petri, menținând în același timp proprietățile sale, și descompunerea [2] , împărțind rețeaua originală în subrețele.

Universal Petri Net

În 1974, Tilak Ajerwala a arătat că rețeaua Petri inhibitoare este un sistem algoritmic universal. În monografia lui Kotov , este dată o schiță a dovezii, indicând regulile de codificare a programului automatului contor al lui Minsky de către o rețea de inhibitori . Peterson oferă exemple de alte clase extinse de rețele Petri care sunt un sistem algoritmic universal: sincron și prioritar. Rețeaua Petri universală construită în mod explicit [3] avea câteva mii de vârfuri și a fost recent redusă la 56 de vârfuri [4] .

Rețele Petri infinite

Rețelele Petri infinite au fost introduse pentru a verifica grilele de calcul și a face posibilă determinarea proprietăților rețelelor Petri pentru structuri regulate (liniare, arbore, pătrate, triunghiulare, hexagonale și hipercube [5] ) de dimensiuni arbitrare, obținute prin compunerea fragmentelor tipice.

Vezi și

Note

  1. ↑ Peterson, 1984 , p. 11 „1.3. Originea teoriei rețelelor Petri.
  2. ↑ Zaitsev D. A. Copie arhivată din 1 aprilie 2022 la Wayback Machine Compositional analysis of Petri nets // Cybernetics and systems analysis. - 2006, nr 1. - S. 143-154.
  3. ↑ Zaitsev D. A. Copie de arhivă din 1 aprilie 2022 la Wayback Machine Universal Petri Net, Cybernetics and System Analysis, nr. 4, 2012, p. 24-39.
  4. ↑ Zaitsev DA Arhivat la 1 aprilie 2022 la Wayback Machine Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1-12.
  5. ↑ Zaitsev D. A. Copie arhivată din 1 aprilie 2022 la Wayback Machine , Shmeleva T. R. Verificarea structurilor de comunicare hipercube prin rețele Petri parametrice, Cybernetics and System Analysis, nr. 1, 2010, pp. 119-128.

Literatură

Link -uri