Petriho síť

Petriho síť  je matematický objekt používaný k modelování dynamických diskrétních systémů, navržený Carlem Petrim v roce 1962 .

Je definován jako bipartitně orientovaný multigraf , skládající se ze dvou typů vrcholů - pozic a přechodů, spojených oblouky. Vrcholy stejného typu nelze připojit přímo. Pozice mohou obsahovat štítky (značky), které se mohou pohybovat po síti. Událostí je spuštění přechodu, při kterém se štítky ze vstupních pozic tohoto přechodu přesunou do výstupních pozic. Události se vyskytují okamžitě nebo v různých časech za určitých podmínek.

Petriho síť je multigraf, protože umožňuje existenci více oblouků z jednoho vrcholu grafu do druhého. Protože jsou oblouky orientované, jedná se o orientovaný multigraf. Vrcholy grafu lze rozdělit na dvě množiny (pozice a přechody) tak, že každý oblouk bude směřovat z prvku jedné množiny (pozice nebo přechody) k prvku jiné množiny (přechody nebo pozice); proto je takový graf bipartitně řízený multigraf.

Původně vyvinut pro modelování systémů s paralelně interagujícími komponentami; Hlavní ustanovení teorie komunikace asynchronních komponent výpočetního systému formuloval Petri ve své doktorské práci „Komunikace automatů“ [1] .

Dynamika

Proces fungování Petriho sítě lze vizuálně znázornit grafem dosažitelných značek. Stav sítě je jednoznačně určen jejím označením – rozložením čipů podle pozice. Vrcholy grafu jsou přípustná označení Petriho sítě, oblouky jsou označeny symbolem spouštěného přechodu. Pro každý excitovaný přechod je postaven oblouk. Konstrukce se zastaví, když dostaneme značky, ve kterých není vybuzen žádný přechod, nebo značky obsažené v grafu. Všimněte si, že graf dosažitelných značek je automat.

Typy Petriho sítí

Některé typy Petriho sítí:

Analýza Petriho sítí

Hlavní vlastnosti Petriho sítě jsou:

Studium těchto vlastností je založeno na analýze dosažitelnosti. Metody analýzy vlastností Petriho sítí jsou založeny na použití grafů dosažitelných (krycích) značek, řešení stavové rovnice sítě a výpočtu lineárních invariantů poloh a přechodů. Pro zmenšení velikosti Petriho sítě při zachování jejích vlastností se používají i pomocné redukční metody a rozklad [2] , rozdělující původní síť na podsítě.

Univerzální Petriho síť

V roce 1974 Tilak Ajerwala ukázal, že inhibiční Petriho síť je univerzálním algoritmickým systémem. V Kotovově monografii je uveden náčrt důkazu, který ukazuje pravidla pro kódování programu Minského čítačového automatu pomocí sítě inhibitorů . Peterson uvádí příklady dalších rozšířených tříd Petriho sítí, které jsou univerzálním algoritmickým systémem: synchronní a prioritní. Explicitně konstruovaná univerzální Petriho síť [3] měla několik tisíc vrcholů a nedávno byla zredukována na 56 vrcholů [4] .

Nekonečné Petriho sítě

Nekonečné Petriho sítě byly zavedeny za účelem ověření výpočtových sítí a umožňujících určit vlastnosti Petriho sítí pro pravidelné struktury (lineární, stromové, čtvercové, trojúhelníkové, šestiúhelníkové a hyperkrychle [5] ) libovolné velikosti, získané skládáním typických fragmentů.

Viz také

Poznámky

  1. ↑ Peterson, 1984 , str. 11 „1.3. Původ teorie Petriho sítí.
  2. ↑ Zaitsev D. A. Archived copy of April 1, 2022 at Wayback Machine Compositional analysis of Petri nets // Kybernetika a analýza systémů. - 2006, č. 1. - S. 143-154.
  3. ↑ Zaitsev D. A. Archivní kopie ze dne 1. dubna 2022 na Wayback Machine Universal Petri Net, Cybernetics and System Analysis, č. 4, 2012, s. 24-39.
  4. ↑ Zaitsev DA Archived 1. dubna 2022 na Wayback Machine Toward the Minimal Universal Petri Network, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1-12.
  5. ↑ Zaitsev D. A. Archived copy of April 1, 2022 at Wayback Machine , Shmeleva T. R. Verification of hypercube communication structure by parameteric Petri nets, Cybernetics and System Analysis, č. 1, 2010, s. 119-128.

Literatura

Odkazy