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"^[1] (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 $P$ és un lloc d'entrada d'una transició $T$ si existeix un arc orientat que connecta aquest lloc a la transició. Un lloc $P$ és un lloc de sortida d'una transició $T$ 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.^[2] 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.^[3]

Definició 1. Una xarxa es una 3-pla $N=(P,T,F)$ on:

$P$ i $T$ són uns conjunts finits i disjunts de llocs i transicions, respectivament.
${\textstyle F\subset (P\times T)\cup (T\times P)}$ és un conjunt d'arcs (o relacions de flux).

Definició 2. Donada una xarxa $N=(P,T,F)$ , una configuració és un conjunt $C$ tal que $C$ ⊆ $P$ .

Definició 3. Una xarxa elemental és aquella en la qual EN = (N, C) on:

$N=(P,T,F)$ és una xarxa.
$C$ C és tal que $C$ ⊆ $P$ é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:

$N=(P,T,F)$ és una xarxa.
$M:P\rightarrow Z$ és un lloc multiconjunt, on $Z$ es un conjunt numerable. $M$ estén el concepte de configuració i comunament es descriu amb referència als diagrames de xarxes de Petri com un marcatge.
$W:F\rightarrow Z$ és un arc multiconjunt, tal que el numerament (o pes) de cada arc és una mesura de la multiplicitat del arc.
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 $Z$ pot ser un conjunt numerable {0,1} i aquells elements en $P$ que mapejen a 1 sota M forma una configuració. Similarment, si una xarxa de Petri no és una xarxa elemental, a llavors un multiconjunt $M$ pot ser interpretat com una representació no singletó d'un conjunt de configuracions. En referència a això, $M$ 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 p₁ és un lloc d'entrada de la transició t; mentres que, el lloc $P$ ₂ és un lloc de sortida de la mateixa transició. Suposem $PN$ ₀ com una xarxa de Petri amb un marcatge configurat com a $M$ ₀ i $PN$ ₁ com una xarxa de Petri amb un marcatge configurat com a $M$ ₁. La configuració de $PN$ N₀ 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 $M$ ₁ en la imatge de $M$ ₀ i resulta en la xarxa de Petri $PN$ ₁, 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 $Z$ 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 $(S,T,W)$ , on:

$S$ és un conjunt finit de llocs.
$T$ és un conjunt finit de transicions.
$S$ i $T$ són disjunts, és a dir, no es pot ser un lloc i una transició a la vegada.
$W:(S\times T)\cup (T\times S)\to \mathbb {N}$ é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: ${\displaystyle F=\{(x,y)\mid W(x,y)>0\}}$ . En multiples llibres, els arcs només poden tenir multiplicitat 1. Aquests llibres usualment defineixen xarxes de Petri utilitzant $F$ en canvi de $W$ . Quan utilitzem aquesta convenció, un graf d'una xarxa de Petri és un multigraf bipartit $(S\cup T,F)$ amb particions de nodes $T$ i $S$ .

La preselecció d'una transició t és un conjunt de llocs d'entrada ${\displaystyle {}^{\bullet }t=\{s\in S\mid W(s,t)>0\}}$ ; la postselecció és el conjunt dels seus llocs de sortida: ${\displaystyle {}^{\bullet }t=\{s\in S\mid W(t,s)>0\}}$ . 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 ${\displaystyle M:S\to \mathbb {N} }$ . Diem que el marcatge assigna a cada lloc un nombre de tokens.

Una xarxa de Petri marcada és una 4-pla ${\displaystyle (S,T,W,M_{0})}$ , on:

${\displaystyle (S,T,W)}$ és un graf d'una xarxa de Petri.
$M_{0}$ é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 $M$ consumeix ${\displaystyle W(s,t)}$ tokens de cadascun dels llocs d'inici $s$ , i produeix ${\displaystyle W(t,s)}$ tokens a cadascun dels llocs de sortida $s$ .
Una transició s'activa (pot iniciar-se) en $M$ si hi han suficients tokens en els llocs d'entrada perquè els consums siguin possibles, és a dir, $\forall s:M(s)\geq W(s,t)$ .

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 ${\displaystyle M{\underset {G}{\longrightarrow }}M'}$ ; podem dir que és accesible des d'M si ${\displaystyle M{\overset {*}{\underset {G}{\longrightarrow }}}M'}$ , on ${\displaystyle {\overset {*}{\underset {G}{\longrightarrow }}}}$ és el tancament transitiu reflexiu de ${\displaystyle {\underset {G}{\longrightarrow }}}$ ; és a dir, que pot ser accesible en 0 o més passos.

Per a una xarxa de Petri (marcada) ${\displaystyle N=(S,T,W,M_{0})}$ , estem interessats en les inicialitzacions que poden ser realitzades començant amb el marcament inicial $M_{0}$ . El conjunt de marcatges accesibles és el conjunt ${\displaystyle R(N)\ {\stackrel {D}{=}}\ \left\{M'{\Bigg |}M_{0}{\xrightarrow[{(S,T,W)}]{*}}M'\right\}}$

L'accesibilitat d'un graf de N és la relació de la transició ${\displaystyle {\underset {G}{\longrightarrow }}}$ restringida al seus marcatges accesibles ${\displaystyle R(N)}$ . É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 $M_{0}$ és una seqüència de transicions ${\displaystyle {\vec {\sigma }}=\langle t_{i_{1}}\cdots t_{i_{n}}\rangle }$ tal que ${\displaystyle M_{0}{\xrightarrow[{G,t_{i_{1}}}]{}}M_{1}\wedge \cdots \wedge M_{n-1}{\xrightarrow[{G,t_{i_{n}}}]{}}M_{n}}$ . El conjunt de seqüències d'inicialització es pot denotar amb $L(N).$

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 $W$ amb un conjunt simple, anomenada la relació de flux, ${\displaystyle F\subseteq (S\times T)\cup (T\times S)}.$

Un altre variació comú, per exemple en Jörge Desel and Gabriel Juhás (2001),^[4] é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 ${\displaystyle (S,T,W,M_{0})}$ poden ser considerats com a vectors d'enters no negatius amb llargada $|S|.$ ^[5]

La seva relació de transició pot ser descrita com un parell de $|S|$ per $|T|$ matrius:

$W^{-}$ , definida per ${\displaystyle \forall s,t:W^{-}[s,t]=W(s,t)}$
${\displaystyle W^{+}}$ , definida per $\forall s,t:W^{+}[s,t]=W(t,s).$

Llavors la seva diferència

$W^{T}=W^{+}-W^{-}$

pot ser utilitzada per descriure els marcatges accesibles en termes de multiplicació de matrius, com segueix. Per qualsevol seqüència de transicions $w$ , s'escriu ${\displaystyle o(w)}$ per al vector que mapeja cada transició al seu nombre d'ocurrències en $w$ . Llavors, tenim

${\displaystyle R(N)=\{M\mid \exists w:M=M_{0}+W^{T}\cdot o(w)\wedge w{\text{ és la sequencia d'inici d'}}N\}}.$

Es requeriment que $w$ sigui una seqüència d'inici; permetre seqüències arbitraries de transicions usualment generarà un conjunt més gran.

${\displaystyle W^{+}={\begin{bmatrix}*&t1&t2\\p1&0&1\\p2&1&0\\p3&1&0\\p4&0&1\end{bmatrix}},\ W^{-}={\begin{bmatrix}*&t1&t2\\p1&1&0\\p2&0&1\\p3&0&1\\p4&0&0\end{bmatrix}},\ W^{T}={\begin{bmatrix}*&t1&t2\\p1&-1&1\\p2&1&-1\\p3&1&-1\\p4&0&1\end{bmatrix}}}$

$M_{0}={\begin{bmatrix}1&0&2&1\end{bmatrix}}$

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)^[6]

Accesibilitat

El problema d'accessibilitat per a xarxes de Petri es decidir, donada una xarxa de Petri $N$ i un marcatge $M$ , si $M\in R(N).$

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.

Tot i que l'accessibilitat sembla una bona eina per trobar estats incorrectes, el graf construït usualment té massa estats que hem de calcular. Per tal d'alleujar aquest problema, es fa servir lògica lineal temporal en conjunt amb un mètode de Tableau per demostrar que no es pot arribar a aquests estats. La lógica lineal temporal utilitza una tècnica de semi-decisió per trobar si un estat és accessible, mitjançant la cerca d'un conjunt de condicions necessàries per a arribar a l'estat i provant que aquestes condicions no poden ser satisfetes.

Vida

Una xarxa de Petri en la qual la transició ${\displaystyle t_{0}}$ es morta, mentres que per totes les $j>0,{\displaystyle t_{j}}$ es $L_{j}$ -viva

Les xarxes de Petri poden tenir diferents nivells de vida ${\displaystyle L_{1}-L_{4}}$ .

Una xarxa de Petri $(N,M_{0})$ es anomenada ${\displaystyle L_{k}}$ -viva només si totes les seves transicions son ${\displaystyle L_{k}}$ -viva, on una transició és:

Considerem mort, si mai pot iniciar-se, per exemple, quan no hi ha cap seqüència d'inici en $L(N,M_{0})$
$L_{1}$ -viva (possible inici), només es podrà iniciar si està en alguna seqüència d'inici en $L(N,M_{0})$
$L_{2}$ -viva només si pot iniciar-se usualment de manera arbitraria, per exemple, si per cada enter positiu k, succeeix almenys kvegades en alguna seqüència d'inici en $L(N,M_{0})$
$L_{3}$ -viva només si s'inicia usualment, per exemple, si per cada enter positiu k, succeeix almenys kvegades en V, per a un determinat set de seqüències d'inici ${\textstyle \textstyle {V\subseteq L(N,M_{0})}}$
$L_{4}$ -viva només si sempre es podrà iniciar, per exemple, es ${\displaystyle L_{1}}$ -viva en tots els marcatges accessibles en $R(N,M_{0})$

Com es pot veure, aquest requeriments son cada vegada més rigorosos que l'anterior: $L_{j+1}$ -viva implica $L_{j}$ -viva per a ${\textstyle \textstyle {j\in {1,2,3}}}.$

Aquestes definicions estan en concordança amb la revisió de Mirata, que utilitza $L_{0}$ -viva com a terme per mort.

Delimitació

Un lloc a una xarxa de Petri es anomenada k-limitada si no conté més de k tokens en tots els seus marcatges accessibles, inclòs el marcatge inicial; es pot dir que és segura si és 1-limitada; és un conjunt limitat si és k-limitat per alguna k.

Una xarxa de Petri marcada s'anomena k-limitada, segura o limitada quan tots els seus llocs ho són. Una xarxa de Petri (graf) s'anomena (estructuralment) limitada si és limitada per tots els possibles marcatges inicials.

Una xarxa de Petri és limitada només si el seu graf d'accessibilitat és finit.

La delimitació és decidible mirant al recobrent, mitjançant la construcció d'un arbre Karp-Miller.

Pot ser útil el fet d'imposar limts en certs llocs d'una xarxa. Aquesta limitació pot ser utilitzada per model·lar sistemes de recursos limitats.

Algunes definicions de les xarxes de Petri permeten aquest fet com un distintiu sintàctic. Formalment, xarxes de Petri amb capacitats de lloc poden ser definides com tuples $(S,T,W,C,M_{0}),$ on $(S,T,W,M_{0})$ és una xarxa de Petri, $C:P\rightarrow \!\!\!\shortmid I\!N$ una assignació de capacitats per a alguns o tots els llocs, i la relació de transició és l'usual restringida als marcatges on cada lloc amb una capacitat té com a molt tots aquells tokens.

Per exemple, si en una xarxa N, ambdós llocs són assignats una capacitat de 2, obtenim una xarxa de Petri amb capacitats als llocs d'N2; el seu graf d'accessibilitat es mostra a la dreta.

Alternativament, podem limitar certs llocs estenen la xarxa. Per ser exacte, es pot fer que un lloc sigui k-limitat afegint un “contra-lloc” amb un flux davant el lloc original, i afegint tokens fent que el total sigui k a ambdós llocs.

Xarxes de Petri discretes, continues i híbrides

Així com existeixen Xarxes de petri per events discrets, també existeixen Xarxes de Petri per processos continus i també per a esdeveniments híbrids (combinació d'events discrets-continus), que s'utilitzen en la teoria de control discreta, contínua i híbrida i per la teoria d'autómats mencionada anteriorment.

Les xarxes de Petri acolorides (CPN) pertanyen a la família de les PN, la diferència és que les consideracions en CPN de colors i de funcions lineals associades als seus arcs. Els tokens de color poden representar un atribut o distintiu, si cal definir dos atributs llavors sorgeix la idea de colors composts.

Una transició en CPN és en estat ACCESIBLE si tots els seus nodes d'entrada contenen un nombre de colors igual o major que els definits per Φ on Φ és una funció lineal associada al node $Pi$ amb la transició $Tj$ . Llavors a més deL concepte de color, aquestes xarxes manegen una funció associada per als elements de les funcions I,O de la PN.

Extensions

Hi ha una gran quantitat d'extensions respecte les xarxes de Petri. Algunes d'aquestes tenen compatibilitat amb versions anteriors de les xarxes de Petri (p.e xarxes de Petri acolorida), algunes afegeixen propietats que no podien ser modelades en les originals (p.e xarxes de Petri amb temps). Encara que els models que posseeixen compatibilitat amb versions anteriors no estenen el poder computacional de les xarxes de Petri, poden tenir representacions més concises i més convenients per modelatge. Extensions que no poden ser transformades en xarxes de Petri poden ser potents, però, no tenen accés al rang d'eines matemàtiques que posseeixen les xarxes de Petri ordinàries.^[7]

El terme xarxa Petri d'alt nivell es usualment utilitzat per referir-se a xarxes que estenen el formalisme bàsic P/T; això inclou xarxes de Petri acolorida, xarxes jeràrquiques com les xarxes dins de xarxes, i totes les extensions mencionades en aquesta secció.

Xarxa de Petri N sense delimitació

Una llista de possibles extensions:

Tipus d'arcs addicionals, dos tipus possibles:
- Un arc de reinici no imposa una precondició al iniciar-se, i buida el lloc on s'inicia la transició; això fa que l'accessibilitat sigui no decidible, mentres que altes propietats, com la terminació, es mantingui decidible.
- Un arc inhibidor imposa una precondició per la qual una transició només s'iniciarà si el lloc esta buit; això permet computacions arbitraries en el nombre de tokens a ser expressats, que realitza el formalisme Turing complert i implica l'existència d'una xarxa universal
En una xarxa de Petri estàndard, els tokens son indistingibles. En una xarxa de Petri acolorida, cada token té un valor propi. En eines populars per a xarxes de Petri acolorida com CPN Tools, els valors dels tokens son escrits, i poden ser testejats(fent servir expressions de guarda) i manipulats amb un llenguatge de programació funcional. Una filial de xarxes de Petri acolorades són les xarxes de Petri ben formades, on l'arc i les expressions de guarda estan restringides amb la finalitat de facilitar l'anàlisi de la xarxa.
Un altre popular extensió de les xarxes de Petri és la jerarquia; això en la forma de distintes vistes i nivells de refinament i abstracció va ser estudiat per Fehling. Un altre form de jerarquia es pot trobar a en l'anomenat objecte xarxa de Petri o sistemes objecte on una xarxa de Petri pot contenir xarxes de Petri com els seus tokens introduint una jerarquia de xarxes de Petri anidades que es comuniquen mitjançant la sincronització de les transicions dels diferents nivells.
Un sistema d'adició de vectors amb estats es un formalisme equivalent a les xarxes de Petri. Malgrat això, pot ser vist com una generalització de les xarxes de Petri. Considerem un autòmat finit on cada transició es etiquetada per una transició d'una xarxa de Petri. La xarxa de Petri a llavors es sincronitzada amb l'autòmat finit, p.e. una transició en l'autòmat es realitza al mateix temps que es faria en una xarxa de Petri. Només es pot realitzar una transició en l'autòmat si la corresponent transició en la xarxa de Petri es iniciada, i només és possible iniciar una transició en una xarxa de Petri si hi ha una transició des de l'estat actual en el qual l'autòmat etiquetat per ell.
Xarxes de Petri prioritzades afegeixen prioritats a les transicions, segons el qual una transició no pot ser iniciada, si una transició de major prioritat es activa (pot iniciar-se). A llavors, les transicions s'agrupen en diferents grups de prioritats, i p.e. un grup de prioritat 3 només podrà iniciar-se si les transicions del grup 1 i 2 no estan actives. Dintre un grup de prioritats, l'inici encara es no determinista.
Xarxa de Petri 2-limitada, obtenida estenen N amb contra-llocs
La prioritat no determinista ha estat una molt valuosa, ja que permet a l'usuari abstraure un gran nombre de propietats (segons per a què es fa servir la xarxa). En alguns casos, malgrat això, es necessita modelar el temps, no només l'estructura del model. Per aquests casos, les xarxes de Petri de temps han evolucionat, on hi ha transicions de temps, i possibles transicions les quals no depenen del temps(si hi ha, les transicions que no depenen del temps tenen una prioritat major respecte les que si ho fan). Una filial de les xarxes de Petri de temps són les xarxes de Petri estocàstiques que afegeixen temps no determinista a través de aleatorietat ajustable de les transicions. La distribució exponencial aleatòria és utilitzada usualment per cronometra aquestes xarxes. En aquest casa, el graf d'accessibilitat d'una xarxa es pot fer servir com una cadena de Markov amb temps continu.
Xarxes de Petri dualistes (Xarxes-dP) es una extensió de les xarxes de Petri desenvolupada per E. Davis, et al. amb la intenció de representar processos de mon real d'una manera més òptima. Les xarxes-dP balançejan la dualitat del canvi/no canvi, acció/passivitat, (transformació) espai/temps, etc., les construccions bipartides de les xarxes de Petri de transformació i lloc resulten en la característica única de la transformació de marcatge, p.e., quan la transformació esta “treballant” es marcada. Això permet a la transformació iniciar-se (o ser marcada) múltiples vegades que representa el comportament del procés al món real. El marcatge de la transformació assumeix que el temps de transformació ha de ser major a zero. Una transformació de temps zero utilitzada usualment en xarxes de Petri pot ser atractiu matemàticament però impracticable a l'hora de representar processos del món real. Xarxes dP també aprofiten el poder de l'abstracció a xarxes de Petri jeràrquiques per tal de representar arquitectura de procés. Sistemes de processos complexos son modelats com un conjunt de xarxes simples interconnectades entre elles amb diferents nivells de jerarquia. El procés d'arquitectura d'un intercanvi de paquets es demostrat en, on els requeriments de desenvolupament son organitzats voltant l'estructura del sistema dissenyat.

Hi ha altres tipus d'extensions de xarxes de Petri, però, es important tenir present que a mesura que la complexitat de la xarxa augmenta en termes de noves propietats, més difícil es fa utilitzar eines estandarditzades per a avaluar certes propietats de la xarxa. Per aquesta raó, es una bona idea utilitzar el tipus de xarxes més simple per modelar una tasca donada.

Restriccions

En comptes d'estendre el formalisme de les xarxes de Petri, també podem restringir la sintaxi d'aquestes per tal d'obtenir certs tipus de xarxes de Petri. Anomenem xarxes de Petri aquelles les quals tots els seus arcs tenen un pes de 1. Amb més restriccions, els següents tipus de xarxes de Petri son estudiades i utilitzades:

En una maquina d'estats, cada transició té un arc d'entrada i sortida, i tots els marcatges tenen exactament un token. Com a conseqüència, no hi pot haver-hi concurrència, però pot succeir conflicte (p.e. no determinisme). Matemàticament: $\forall t\in T:|t^{\bullet }|=|{}^{\bullet }t|=1$
En un graf marcat, tot lloc te un arc d'entrada i un de sortida. Això significa, que no hi pot existir conflicte, però pot existir concurrència. Matemàticament: $\forall s\in S:|s^{\bullet }|=|{}^{\bullet }s|=1$
En una xarxa de lliure elecció, cada arc d'un lloc a una transició es o només l'arc d'aquest lloc o només l'arc cap a aquesta transició. P.e. pot haver-hi concurrència i conflicte, però no ambdós al mateix temps. Matemàticament: $\forall s\in S:(|s^{\bullet }|\leq 1)\vee ({}^{\bullet }(s^{\bullet })=\{s\})$
Lliure elecció estesa – una xarxa de Petri que pot ser transformada en una xarxa de lliure elecció.
En una xarxa d'elecció asimètrica, concurrència i conflicte pot ocórrer, però no simètricament. Matemàticament: $\forall s_{1},s_{2}\in S:(s_{1}{}^{\bullet }\cap s_{2}{}^{\bullet }\neq \emptyset )\to [(s_{1}{}^{\bullet }\subseteq s_{2}{}^{\bullet })\vee (s_{2}{}^{\bullet }\subseteq s_{1}{}^{\bullet })]$

Xarxes de flux de treball

Les xarxes de flux de treball son una subclasse de les xarxes de Petri creades amb la intenció de modelar el flux de treball de les activitats procés. Les transicions de les xarxes de flux de treball son assignades a tasques o activitats, i els llocs son assignats a les pre/post condicions. Les xarxes de flux de treball tenen requeriments estructurals i operacionals addicionals, principalment l'addició d'una únic lloc d'entrada sense transicions prèvies i un lloc de sortida sense transicions addicionals. D'aquesta manera, els marcatges d'inici i finalització representen l'estat del procés.

Les xarxes de flux de treball tenen la propietat de solidesa, indicant que un procés el qual s'inicia amb un marcatge de k tokens en el lloc d'inici, pot arribar al lloc final amb un total de k tokens. Addicionalment, totes les transicions del procés podrien iniciar-se (p.e. per a cada transició hi ha un estat accessible en el qual la transició està habilitada).

Un camí dirigit en una xarxa de Petri està definit com una seqüència de nodes (llocs i transicions) enllaçats pels arcs dirigits. Un camí elemental inclou cada node en la seqüència una única vegada.

Una xarxa de Petri ben manejada es una xarxa en la qual no hi ha camins elementals totalment distints entre un lloc i una transició (o viceversa), p.e., si hi ha dos camins entre un parell de nodes, a llavors, aquests camins comparteixen un node. Una xarxa de flux de treball ben manejada i acíclica és sòlida.

Les xarxes de flux de treball esteses son xarxes de Petri compostes de xarxes de flux de treball amb una transició addicional t. El lloc de sortida esta connectat com el lloc d'entrada de la transició t i el lloc d'origen del lloc de sortida. L'inici de la transició causa la iteració del procés.

La matriu d'estructura de disseny (DSM) pot modelar les relacions de procés i poden servir per planejament de procés. Les xarxes DSM són la realització de plans basat en DSM transformats en processos de flux per a xarxes de Petri. La construcció de xarxes DSM asseguren la propietat de solides de la xarxa resultant.

Vegeu també

Referències

↑ Petri, Carl Adam «Kommunikation mit Automaten». http://edoc.sub.uni-hamburg.de/informatik/volltexte/2011/160/pdf/diss_petri_d.pdf, 1962.
↑ Karp, R. M. «On the Computational Complexity of Combinatorial Problems» (en anglès). Networks, 5, 1, 1975, pàg. 45–68. DOI: 10.1002/net.1975.5.1.45. ISSN: 1097-0037.
↑ «Petri Nets for Dynamic Event-Driven System Modeling».
↑ Desel, Jörg; Juhás, Gabriel. “What Is a Petri Net?” Informal Answers for the Informed Reader (en anglès). Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, p. 1–25. DOI 10.1007/3-540-45541-8_1. ISBN 9783540455417.
↑ «“What Is a Petri Net?” | Informal Answers for the Informed Reader».
↑ Esparza, Javier. Decidability and complexity of Petri net problems — An introduction (en anglès). Berlin, Heidelberg: Springer Berlin Heidelberg, 1998, p. 374–428. DOI 10.1007/3-540-65306-6_20. ISBN 9783540494423.
↑ «A Study of Petri Nets | Modeling, Analysis and Simulation». Arxivat de l'original el 2019-05-25. [Consulta: 25 maig 2019].

Decidability Issues for Petri Nets a survey. Javier Esparza, Mogens Nielsen 1.994
Harald Störrle, Models of Software Architecture - Design and Analysis with UML and Petri-Nets , Books on Demand GmbH, ISBN 3-8311-1330-0
Robert-Christoph Riemann, Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus , Herbert Utz Verlag, ISBN 3-89675-629-X
Kurt Jensen, Coloured Petri Nets , Springer Verlag, ISBN 3-540-62867-3
Janette Cardoso, Heloisa Camargo, Fuzziness in Petri Nets , Physica-Verlag, ISBN 3-7908-1158-0
James Lyle Peterson, Petri Net Theory and the Modeling of Systems , Prentice Hall, ISBN 0136619835
Mengchu Zhou, Frank Dicesare, Petri Net Synthesis for Discrete Event Control of Manufacturing Systems , Kluwer Academic Publishers, ISBN 0792392892
Mengchu Zhou: Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach , World Scientific Publishing Company, ISBN 981023029X

Enllaços externs

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Xarxa de Petri

YASPER Process Modeling Software
Petri Net Markup Language Arxivat 2010-01-07 a Wayback Machine.
exchange Routing Language Arxivat 2004-12-09 a Wayback Machine.
Citations from CiteSeer
Introducció a les xarxes de Petri. Aplicació pràctica en multitasca. Arxivat 2007-03-14 a Wayback Machine.

[1] Petri, Carl Adam «Kommunikation mit Automaten». http://edoc.sub.uni-hamburg.de/informatik/volltexte/2011/160/pdf/diss_petri_d.pdf, 1962.

[2] Karp, R. M. «On the Computational Complexity of Combinatorial Problems» (en anglès). Networks, 5, 1, 1975, pàg. 45–68. DOI: 10.1002/net.1975.5.1.45. ISSN: 1097-0037.

[3] «Petri Nets for Dynamic Event-Driven System Modeling».

[4] Desel, Jörg; Juhás, Gabriel. “What Is a Petri Net?” Informal Answers for the Informed Reader (en anglès). Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, p. 1–25. DOI 10.1007/3-540-45541-8_1. ISBN 9783540455417.

[5] «“What Is a Petri Net?” | Informal Answers for the Informed Reader».

[6] Esparza, Javier. Decidability and complexity of Petri net problems — An introduction (en anglès). Berlin, Heidelberg: Springer Berlin Heidelberg, 1998, p. 374–428. DOI 10.1007/3-540-65306-6_20. ISBN 9783540494423.

[7] «A Study of Petri Nets | Modeling, Analysis and Simulation». Arxivat de l'original el 2019-05-25. [Consulta: 25 maig 2019].

[1]

[2]

[3]

[4]

[5]

[6]

[7]