Petri nät

Petri-nätet  är ett matematiskt objekt som används för att modellera dynamiska diskreta system , föreslog av Carl Petri 1962 .

Det definieras som en tvådelad orienterad multigraf , bestående av två typer av hörn - positioner och övergångar, förbundna med bågar. Vertices av samma typ kan inte kopplas direkt. Positioner kan innehålla etiketter (markörer) som kan flytta runt i nätverket. En händelse är avfyrandet av en övergång, där etiketterna från ingångspositionerna för denna övergång flyttas till utgångspositionerna. Händelser inträffar omedelbart eller vid olika tidpunkter, under vissa förhållanden.

Petri-nätet är en multigraf, eftersom det tillåter förekomsten av flera bågar från en vertex av grafen till en annan. Eftersom bågarna är riktade är detta en riktad multigraf. Grafens hörn kan delas in i två uppsättningar (positioner och övergångar) på ett sådant sätt att varje båge kommer att riktas från ett element i en uppsättning (positioner eller övergångar) till ett element i en annan uppsättning (övergångar eller positioner); därför är en sådan graf en tvådelad multigraf.

Ursprungligen utvecklad för modelleringssystem med parallellt interagerande komponenter; Petri formulerade huvudbestämmelserna i teorin om kommunikation av asynkrona komponenter i ett datorsystem i sin doktorsavhandling "Communication of automata" [1] .

Dynamics

Processen för Petri-nätets funktion kan visuellt representeras av en graf över nåbara markeringar. Nätverkets tillstånd bestäms unikt av dess märkning - fördelningen av chips efter position. Grafens hörn är tillåtna markeringar av Petri-nätet, bågarna är markerade med den utlösta övergångssymbolen. En båge byggs för varje exciterad övergång. Konstruktionen stannar när vi får markeringar där ingen övergång är exciterad, eller markeringar som finns i grafen. Observera att grafen över nåbara markeringar är en automat.

Typer av petrinät

Några typer av petrinät:

Analys av Petri-nät

De viktigaste egenskaperna hos ett Petri-nät är:

Studiet av dessa egenskaper baseras på nåbarhetsanalys. Metoder för att analysera egenskaperna hos petrinät är baserade på användningen av grafer över nåbara (täckande) markeringar, lösning av ekvationen av nätets tillstånd och beräkning av linjära invarianter av positioner och övergångar. Hjälpreduktionsmetoder används också för att minska storleken på Petri-nätet samtidigt som dess egenskaper bibehålls och sönderdelning [2] , vilket delar upp det ursprungliga nätet i subnät.

Universal Petri Net

1974 visade Tilak Ajerwala att det hämmande Petri-nätet är ett universellt algoritmiskt system. I Kotovs monografi ges en skiss av beviset, som indikerar reglerna för att koda programmet för Minskys motautomat av ett inhibitornätverk . Peterson ger exempel på andra utökade klasser av petrinät som är ett universellt algoritmiskt system: synkront och prioriterat. Det explicit konstruerade universella Petri-nätet [3] hade flera tusen hörn och reducerades nyligen till 56 hörn [4] .

Infinite Petri Nets

Oändliga Petri-nät introducerades för att verifiera beräkningsnät och göra det möjligt att bestämma egenskaperna hos Petri-nät för vanliga strukturer (linjära, trädliknande, kvadratiska, triangulära, hexagonala och hyperkuber [5] ) av godtycklig storlek, erhållna genom att komponera typiska fragment.

Se även

Anteckningar

  1. ↑ Peterson, 1984 , s. 11 "1.3. Ursprunget till teorin om Petri nät.
  2. ↑ Zaitsev D. A. Arkiverad kopia av 1 april 2022 på Wayback Machine Kompositionsanalys av Petri-nät // Cybernetik och systemanalys. - 2006, nr 1. - S. 143-154.
  3. ↑ Zaitsev D. A. Arkivkopia daterad 1 april 2022 på Wayback Machine Universal Petri Net, Cybernetics and System Analysis, nr 4, 2012, sid. 24-39.
  4. ↑ Zaitsev DA Arkiverad 1 april 2022 på Wayback Machine Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1-12.
  5. ↑ Zaitsev D. A. Arkiverad kopia av 1 april 2022 på Wayback Machine , Shmeleva T. R. Verifiering av hyperkubkommunikationsstrukturer av parametriska petrinät, Cybernetics and System Analysis, nr 1, 2010, s. 119-128.

Litteratur

Länkar