miniatura|Trajectòria d'una xarxa de Petri Una Xarxa de Petri, també coneguda com una xarxa de lloc / transició, és un llenguatge matemàtic de modelatge per a la descripció de sistemes distribuïts discrets. Van ser ideades cap al 1960 per Carl Adam Petri. Són una generalització de la teoria d'autòmats que permet expressar activitats concurrents. També són conegudes com a PN (Petri Net).
En la seva tesi doctoral "kommunikation mitautomaten" (Comunicació amb autòmats), estableix els fonaments per al desenvolupament teòric dels conceptes bàsics de les PN.
Una xarxa de petri es un graf dirigit bipartit, en el qual els nodes representen transicions (representades amb una barra vertical) i llocs (representats amb un cercle). Els arcs, descriuen la relació entre transicions i llocs.
Les xarxes de Petri ofereixen una notació gràfica de processos pas a pas, que inclouen decisions, iteracions, i execucions concurrents. A diferència d'altres estàndards, com per exemple diagrames UML o els Model i Notació de Processos de Negoci (Business Process Model and Notation), les xarxes de petri tenen una notació matemàtica exacta de la seva semàntica d'execució, a més de teoria matemàtica per a l'anàlisi de processos.
Principis d'una xarxa de Petri Una xarxa de Petri està formada per llocs, transicions i arcs. Els arcs es dirigeixen des d'un lloc fins a una transició i viceversa, però no entre llocs o transicions. Els llocs els quals un arc es dirigeix a una transició s'anomenen llocs d'entrada d'una transició. Els arcs que s'originen en una transició s'anomenen llocs de sortida d'una transició.
Parlant abstractament de les xarxes de Petri, una transició d'una xarxa de Petri s'iniciarà si aquesta està habilitada, per exemple, si hi ha suficients tokens en els llocs d'entrada corresponents; quan la transició s'inicia, aquesta consumeix els tokens d'entrada requerits i en conseqüència crea tokens en el lloc de sortida. Aquesta transició es atòmica.
L'execucció d'una xarxa de Petri en general no es determinística, tot i que s'hi pot determinar una política d'execució definida prèviament. El no determinisme vol dir que, en cas que múltiples accions estiguin disponibles al mateix temps, qualsevol pot ser executada.
Com que la transició no es deteministica i múltiples tokens poden estar en el mateix lloc, les xarxes de Petri son adequades per model·lar el comportament concurrent de sistemes distribuïts.
Regla de l'evolució. Un lloc és un lloc d'entrada d'una transició si existeix un arc orientat que connecta aquest lloc a la transició. Un lloc és un lloc de sortida d'una transició si existeix un arc orientat que connecta aquesta transició al lloc.
La circulació per una xarxa de petri, es fa mitjançant unes fitxes o tokens. Gràficament, els llocs d'una xarxa de Petri poden contenir un nombre discret de fitxes. Qualsevol distribució de tokens als llocs representen una configuració anomenada marcatge.
En la seva forma més bàsica, les fitxes que circulen en una xarxa de Petri són totes idèntiques. Es pot definir una variant de les xarxes de Petri en les quals les fitxes poden tenir un color (una informació que les distingeix), un temps d'activació i una jerarquia a la xarxa.
La majoria dels problemes sobre xarxes de Petri són decidibles, com ara el caràcter tancat i la cobertura. Per a resoldre'ls s'utilitza un arbre de Karp-Miller. Se sap que el problema d'abast és decidible, almenys en un temps exponencial.
Definició formal i terminologia bàsica Les xarxes de Petri son sistemes basats en estats i transicions que estenen una classe de xarxes anomenades xarxes elementals.
Definició 1. Una xarxa es una 3-pla on: i són uns conjunts finits i disjunts de llocs i transicions, respectivament. és un conjunt d'arcs (o relacions de flux). miniatura|Xarxa de Petri amb una transició habilitada Definició 2. Donada una xarxa , una configuració és un conjunt tal que ⊆ .
Definició 3. Una xarxa elemental és aquella en la qual EN = (N, C) on: és una xarxa. C és tal que ⊆ és una configuració. Definició 4. Una xarxa de Petri és aquella la qual té forma PN = (N, M, W) i estén aquesta xarxa elemental tal que: és una xarxa. és un lloc multiconjunt, on es un conjunt numerable. estén el concepte de configuració i comunament es descriu amb referència als diagrames de xarxes de Petri com un marcatge. és un arc multiconjunt, tal que el numerament (o pes) de cada arc és una mesura de la multiplicitat del arc.miniatura|Xarxa de Petri resultant després d'iniciar-se la transició (xarxa inicial en la figura de dalt)
Si una xarxa de petri és equivalent a una xarxa elemental, llavors pot ser un conjunt numerable {0,1} i aquells elements en que mapejen a 1 sota M forma una configuració. Similarment, si una xarxa de Petri no és una xarxa elemental, a llavors un multiconjunt pot ser interpretat com una representació no singletó d'un conjunt de configuracions. En referència a això, estén el concepte de configuració de xarxes elementals a xarxes de Petri.
En el diagrama d'una xarxa de Petri, els llocs són representats com a cercles, les transicions com a rectangles allargats i els arcs com a fletxes unidireccionals que mostren les connexions de llocs a transicions i viceversa. Si el diagrama fos d'una xarxa elemental, llavors els llocs en una configuració serien representats com a cercles, on cada cercle conté un únic punt anomenat token. En el diagrama de la xarxa de Petri, el cercle pot contenir més d'un token per tal de mostrar el nombre de vegades que un lloc apareix en una configuració.
A la figura de dalt, el lloc p1 és un lloc d'entrada de la transició t; mentres que, el lloc ₂ és un lloc de sortida de la mateixa transició. Suposem 0 com una xarxa de Petri amb un marcatge configurat com a 0 i 1 com una xarxa de Petri amb un marcatge configurat com a 1. La configuració de N0 habilita la transició t a través de la propietat que fa que tots els llocs d'entrada tenen un nombre de tokens suficients (representats com a punts) “igual o major” que la multiplicitat dels seus arcs respectius. Quan es dona el cas esmentat, la transició s'habilitará i iniciará. En aquest exemple, l'inici de la transició t genera un mapa que té el marcatge configurat 1 en la imatge de 0 i resulta en la xarxa de Petri 1, vista en el diagram de sota.
Al diagrama, la regla d'inici per una transició pot ser caracteritzada per una subtracció d'un nombre de tokens d'un lloc d'entrada igual a la multiplicitat dels respectius arcs d'entrada i acumulant un nombre de tokens als llocs de sortida igual a la multiplicitat dels arcs de sortida respectius.
Observació. El significat precís de “igual o major” dependrá de les propietats algebraiques de la suma aplicades en en la regla d'inici, on subtils variacions de les propietats algebraiques poden dirigir a altres classes de xarxes de Petri; com per exemple les xarxes de Petri Algebraiques.
Sintaxi Un graf d'una xarxa de Petri és una 3-pla , on:
és un conjunt finit de llocs. és un conjunt finit de transicions. i són disjunts, és a dir, no es pot ser un lloc i una transició a la vegada. és un multiconjunt d'arcs, és a dir, li assigna a cada arc un enter no negatiu(també anomenat pes); un arc no pot connectar dues transicions o llocs.
La relació de flux és el conjunt d'arcs: . En multiples llibres, els arcs només poden tenir multiplicitat 1. Aquests llibres usualment defineixen xarxes de Petri utilitzant en canvi de . Quan utilitzem aquesta convenció, un graf d'una xarxa de Petri és un multigraf bipartit amb particions de nodes i .
La preselecció d'una transició t és un conjunt de llocs d'entrada ; la postselecció és el conjunt dels seus llocs de sortida: . Definicions de pre i postseleccions de llocs són anàlogues.
El marcament d'una xarxa de Petri (graf) és un multiconjunt de llocs, és a dir, un mapeig . Diem que el marcatge assigna a cada lloc un nombre de tokens.
Una xarxa de Petri marcada és una 4-pla , on: és un graf d'una xarxa de Petri. és el marcatge inicial, el marcatge d'un graf d'una xarxa de Petri.
Semàntica d'execució En paraules: Iniciar una transició t en un marcatge consumeix tokens de cadascun dels llocs d'inici , i produeix tokens a cadascun dels llocs de sortida . Una transició s'activa (pot iniciar-se) en si hi han suficients tokens en els llocs d'entrada perquè els consums siguin possibles, és a dir, . Generalment, estem interessats en el qual pot succeir quan les transicions poden iniciarse contínuament en un ordre arbitrari.
Diem que el marcatge M’ és accesible des d'un marcatge M en un pas si ; podem dir que és accesible des d'M si , on és el tancament transitiu reflexiu de ; és a dir, que pot ser accesible en 0 o més passos.
Per a una xarxa de Petri (marcada) ', estem interessats en les inicialitzacions que poden ser realitzades començant amb el marcament inicial . El conjunt de marcatges accesibles és el conjunt
Laccesibilitat d'un graf de N és la relació de la transició restringida al seus marcatges accesibles . És l'espai d'estats de la xarxa.
Una seqüència d'inicialització per una xarxa de Petri amb un graf G i marcatge inicial és una seqüència de transicions tal que . El conjunt de seqüències d'inicialització es pot denotar amb
Variacions en la definició Com s'ha comentat, una variació comú és la de no permetre la multiplicitat d'arcs i reemplaçar el multiconjunt d'arcs amb un conjunt simple, anomenada la relació de flux,
Un altre variació comú, per exemple en Jörge Desel and Gabriel Juhás (2001), és la de permetre capacitats ser definides com a llocs. Això es discutit a les extensions d'avall.
Formulació Els marcatges d'una xarxa de Petri poden ser considerats com a vectors d'enters no negatius amb llargada
La seva relació de transició pot ser descrita com un parell de per matrius: , definida per , definida per Llavors la seva diferència
pot ser utilitzada per descriure els marcatges accesibles en termes de multiplicació de matrius, com segueix. Per qualsevol seqüència de transicions , s'escriu per al vector que mapeja cada transició al seu nombre d'ocurrències en . Llavors, tenim
miniatura|Example de xarxa de Petri Es requeriment que sigui una seqüència d'inici; permetre seqüències arbitraries de transicions usualment generarà un conjunt més gran.
Propietats matemàtiques de les xarxes de Petri Una de les propietats més interessants de les xarxes de petri és que donen un balanç entre poder de modelatge i d'anàlisi. Moltes aplicacions de sistemes concurrents es poden determinar mitjançant xarxes de Petri, encara que el cost de les operacions sigui molt costós. S'ha determinat que multiples subclasses de xarxes de Petri poden modelar diferent classes de sistemes concurrents, a la vegada que aquests problemes es fan més senzills.
Una revisió d'aquests problemes de decisió, amb resultats de decidibilitat o complexitat per a xarxes de Petri i algunes subclasses, pot ser trobat a Javier Esparza i Mogens Nielsen (1995)
Accesibilitat El problema d'accessibilitat per a xarxes de Petri es decidir, donada una xarxa de Petri i un marcatge , si
Clarament, aquest és un problema on recorrem el graf d'accessibilitat definit a dalt, fins que arribem al marcatge demanat o sapiguem que no es pot trobar. Aquesta tasca és més complexa del que sembla a primera vista: el graf d'accessibilitat és generalment infinit, per això és difícil determinar quan es pot aturar.
De fet, aquest problema s'ha determinat que és EXSPACE-hard anys abans que es determinés si era decidible.