Rete di Petri

Una rete di Petri (conosciuta anche come rete posto/transizione o rete P/T) è una delle varie rappresentazioni matematiche di un sistema distribuito discreto. Come un linguaggio di modellazione, esso descrive la struttura di un sistema distribuito come un grafo bipartito con delle annotazioni.

La rete di Petri deve il suo nome al matematico tedesco Carl Adam Petri, il quale ne enunciò le caratteristiche per la prima volta nel 1962 tramite la pubblicazione della propria tesi di dottorato, intitolata Kommunikation mit Automaten. Come rivelato dallo stesso Petri nel 2007, l'idea alla base della rete di Petri fu da lui concepita già nell'agosto 1939 (quando aveva 13 anni) per memorizzare in maniera più efficace i processi chimici.^[1][2][3]

Descrizione

Concetti base

Una rete di Petri PT (Place/Transition) è un grafo orientato con due tipi di nodi, posti e transizioni, connessi da archi diretti. I posti sono rappresentati graficamente da cerchi e le transizioni da rettangoli.

Un arco può unire solamente nodi di tipo diverso, quindi possono esserci archi tra posti e transizioni - ma non tra posti e posti o transizioni e transizioni. Un posto da cui un arco parte per finire in una transizione è detto posto di input della transizione; un posto in cui un arco arriva partendo da una transizione è detto posto di output della transizione.

I posti possono contenere un certo numero di token o marche. Una distribuzione di token sull'insieme dei posti della rete è detta marcatura. Le transizioni agiscono sui token in ingresso secondo una regola, detta regola di scatto (in inglese firing). Una transizione è abilitata se può scattare, cioè se ci sono token in ogni posto di input. Quando una transizione scatta, essa consuma token dai suoi posti di input, esegue dei task e posiziona un numero specificato di token in ognuno dei suoi posti di uscita. Ciò avviene automaticamente, ad esempio in un singolo step non-prelazionabile. L'esecuzione delle reti di Petri è non deterministica. Ciò significa due cose:

1. se più transizioni sono abilitate nello stesso momento, una qualsiasi di esse può scattare
2. non è garantito che una transizione abilitata scatti; una transizione abilitata può scattare immediatamente, dopo un tempo di attesa qualsiasi (a patto che resti abilitata), o non scattare affatto.

Poiché lo scatto di una transizione non è predicibile a priori, le reti di Petri sono molto adatte a modellare il comportamento di un sistema concorrente.

Definizione formale

Una rete di Petri è un sistema a transizione di stati che estende una classe di reti, dette reti elementari.^[4]

Definizione 1: Una rete è una tripla ${\displaystyle N=(P,T,F)}$ dove:

1. ${\displaystyle P}$ è un insieme di stati chiamati posti.
2. ${\displaystyle T}$ è un insieme di transizioni.
3. ${\displaystyle F\subset (P\times T)\bigcup (T\times P)}$ è un insieme di flussi relazionali chiamati “archi”. Tali flussi sono possibili solamente tra posti e transizioni o viceversa.

Una rete è un grafo bipartito, dove ${\displaystyle P}$ è una partizione e ${\displaystyle T}$ è l'altra. Più precisamente, per ogni ${\displaystyle t}$ in ${\displaystyle T}$ esistono ${\displaystyle p}$ e ${\displaystyle q}$ in ${\displaystyle P}$ tali che ${\displaystyle (p,t)}$ e ${\displaystyle (t,q)}$ appartengono ad ${\displaystyle F}$ e per ogni ${\displaystyle p}$ e ${\displaystyle q}$ in ${\displaystyle P}$ se ${\displaystyle (p,t)}$ e ${\displaystyle (t,q)}$ sono in ${\displaystyle F}$ allora ${\displaystyle p\neq q}$. In formula:

${\displaystyle \forall t\in T\,\,\exists p,q\in P\,\,t.c.\,\,(p,t),(t,q)\in F\,p\neq q}$

L'insieme ${\displaystyle P\bigcup T}$ contiene gli elementi della rete. L'insieme dei posti definisce gli stati locali della rete, tuttavia, lo stato globale di una rete può essere definito da sottoinsiemi di posti.

Definizione 2: Data una rete ${\displaystyle N=(P,T,F)}$ , una configurazione è un insieme ${\displaystyle C\subseteq P}$.

Definizione 3: Una rete elementare è una rete della forma ${\displaystyle EN=(N,C)}$ dove:

1. ${\displaystyle N=(P,T,F)}$ è una rete.
2. ${\displaystyle C\subseteq P}$ è una configurazione.

Definizione 4: Una rete di Petri è una rete della Teoria delle reti di Petri. Le proprietà teoriche delle reti di Petri sono state studiate ampiamente. Un motivo principale per usare le reti di Petri nel modellare i sistemi concorrenti è dato dalla possibilità di delineare formalmente e decidere delle proprietà desiderabili del sistema, come la liveness (ad esempio, in un sistema che non deve mai bloccarsi) o la boundedness (ad esempio, le risorse di un sistema come la CPU sono limitate). Naturalmente, la stessa proprietà in un contesto diverso può assumere un significato completamente diverso.

Una marcatura in una rete di Petri è raggiungibile se, partendo dalla marcatura iniziale, esiste una sequenza di scatto che la produce. Una rete di Petri è bounded se c'è un limite massimo al numero di token nelle sue marcature raggiungibili.

Tipi principali

Ci sono sei tipi principali delle reti di Petri:

1. Macchina a stati finiti (State Machine - SM) - in cui ogni transizione ha un solo arco entrante e un solo arco uscente. Ciò implica che non può esserci concorrenza ma può esserci conflitto (ovvero quando si pone la domanda: dove deve andare il token di un posto? In una o nell'altra transizione?). Matematicamente: ${\displaystyle \forall t\in T:|t\bullet |=|\bullet t|=1}$
2. Grafo marcato (Marked Graph - MG) - in cui ogni posto ha un solo arco entrante e un solo arco uscente. In questo caso non ci sono conflitti ma ci sono concorrenze. Matematicamente: ${\displaystyle \forall p\in P:|p\bullet |=|\bullet p|=1}$
3. Scelta libera (Free choice - FC) - in cui l'arco è o l'unico arco che esce da un posto oppure l'unico arco che entra in una transizione. In altre parole, ci può essere sia concorrenza sia conflitto, ma non nello stesso istante. Matematicamente: ${\displaystyle \forall p\in P:(|p\bullet |\leq 1)\vee (\bullet (p\bullet )=\{p\})}$
4. Scelta libera estesa (Extended free choice - EFC) - una rete di Petri che può essere trasformata in una FC.
5. Scelta asimmetrica (Asymmetric choice - AC) - concorrenza e conflitto (insomma, confusion), ma non asimmetricamente. Matematicamente: ${\displaystyle \forall p_{1},p_{2}\in P:(p_{1}\bullet \cap p_{2}\bullet \neq 0)\to [(p_{1}\bullet \subseteq p_{2}\bullet )\vee (p_{2}\bullet \subseteq p_{1}\bullet )]}$

Estensioni

Esistono molte estensioni delle reti di Petri. Alcune di esse sono completamente retro-compatibili (ad esempio le reti di Petri colorate) con la rete di Petri originaria, altre aggiungono proprietà che non possono essere modellate nella rete di Petri d'origine (ad esempio le reti di Petri tempificate). Se esse possono essere modellate nella rete di Petri originale, esse non sono reali estensioni ma sono modi conveniente di far vedere la stessa cosa, e possono essere trasformate con opportune formule matematiche nell'originale rete, senza perdere di significato.^[5] Le estensioni che non possono essere trasformate sono a volte rappresentazioni molto potenti, ma tipicamente perdono una quantità di tools matematici disponibili per analizzare le normali reti di Petri.

Il termine rete di Petri ad alto livello è usato per molti formalismi delle reti di Petri che estendono il formalismo base P/T. Questo include anche le reti di Petri colorate, gerarchiche e tutte le altre estensioni citate in questa sezione.

Una breve lista delle possibili estensioni:

• In una rete di Petri standard, i token sono indistinguibili. In una rete di Petri colorata, ogni token ha un valore.^[6] Nei tool popolari per le reti di Petri colorate, come CPN Tool, il valore del token è tipizzato e può essere testato e manipolato con un linguaggio di programmazione funzionale. Un sussidiario delle reti di Petri colorate sono le reti di Petri well-formed, dove le espressioni degli archi e di controllo sono vincolate a rendere più semplice l'analisi della rete.
• Un'altra estensione popolare della rete di Petri è la gerarchia: la gerarchia nella forma di diverse viste che supportano vari livelli di rifinimento e astrazione furono studiate da Fehling. Un'altra forma di gerarchia si trova nelle cosiddette reti di Petri ad oggetti o nei sistemi ad oggetti, dove una rete di Petri può contenere diverse reti come suoi token, stabilendo una gerarchia di reti di Petri innestate che comunicano sincronizzando le transizioni su diversi livelli.^[7]
• Un Vector Addition System with States (VASS) può essere vista come generalizzazione di una rete di Petri (ma con qualcosa in meno). Si consideri un automa a stati finiti dove ogni transizione è tradotta in una transizione della rete di Petri. La rete di Petri segue dunque l'evoluzione dell'automa, ovvero una transizione nell'automa è eseguita allo stesso tempo nella corrispondente transizione nella rete di Petri. È possibile eseguire una transizione nell'automa solo se la corrispondente transizione nella rete è abilitata; è possibile che la transizione nella rete di Petri scatti solo se c'è una transizione dal corrente stato dell'automa etichettata da essa. Quello che gli automi a stati finiti non possono rappresentare sono le situazioni di sincronizzazioni che invece sono presenti nella rete di Petri: ad esempio, quando due posti sono in attesa su una transizione e la transizione non può scattare fin quando i due posti non rispondono entrambi ai vincoli della transizione.
• Le reti di Petri con priorità aggiungono meccanismi di priorità alle transizioni, in base a cui una transizione non può scattare se una transizione di priorità più alta è abilitata. Le transizioni sono divise in gruppi di priorità, ad esempio il gruppo di priorità 3 può solo scattare se tutte le transizioni nel gruppo 1 e nel gruppo 2 sono disabilitate. Con un gruppo di priorità, lo scatto è ancora non deterministico.
• La proprietà non-deterministica è di grande rilievo, poiché consente all'utente di astrarre un gran numero di proprietà (dipende dall'uso che bisogna fare della rete). In alcuni casi inoltre è necessario aggiungere al modello una tempificazione. Nascono così le reti di Petri temporizzate, nelle quali ci sono delle transizioni che sono temporizzate e altre che non lo sono (tipicamente le transizioni senza tempificazione hanno una priorità più alta di quelle temporizzate). Si vedano anche le reti di Petri stocastiche che aggiungono un tempo non-deterministico per rendere un concetto di casualità delle transizioni. La distribuzione casuale esponenziale è tipicamente utilizzata per "tempificare" tali reti. In questo caso, il grafo di raggiungibilità della rete diventa una catena di Markov.
• Le reti di Petri dualistiche (dP-Nets) sono un'estensione delle reti di Petri sviluppata da E. Dawis et al.^[8] per rappresentare meglio i processi del mondo reale. Le reti dP bilanciano la dualità di cambiamento/non cambiamento, azione/passività, tempo/spazio (di trasformazione), ecc., tra i costrutti bipartiti di trasformazione e luogo della rete di Petri, risultando nella caratteristica unica della marcatura della trasformazione, ossia quando la trasformazione è "funzionante" essa viene marcata. Ciò consente alla trasformazione di attivarsi (o essere marcata) più volte, rappresentando il comportamento nel mondo reale della portata del processo. La marcatura della trasformazione presuppone che il tempo di trasformazione debba essere maggiore di zero. Un tempo di trasformazione pari a zero, utilizzato in molte tipiche reti di Petri, può essere matematicamente attraente ma poco pratico nel rappresentare i processi del mondo reale. Le reti dP sfruttano anche la potenza dell'astrazione gerarchica delle reti di Petri per rappresentare l'architettura dei processi. I sistemi di processi complessi sono modellati come una serie di reti più semplici interconnesse attraverso vari livelli di astrazione gerarchica. È stata dimostrata l'architettura del processo di una commutazione di pacchetto,^[9] dove i requisiti di sviluppo sono organizzati attorno alla struttura del sistema progettato.

Ci sono molte altre estensioni alla rete di Petri, ma è importante ricordare che quanto più aumenta la complessità della rete in termini di proprietà estese, tanto più difficile è usare i tools standard per valutare certe proprietà della rete. Per questa ragione, è una buona idea usare il tipo di rete più semplice possibile per un dato processo di modellizzazione.

Modelli successivi di concorrenza

Successivamente all'invenzione delle reti di Petri, altri modelli di concorrenza, che sono basati sullo scambio di messaggi e sul comportamento composizionale, sono stati introdotti. Robin Milner e Carl Hewitt hanno infatti sostenuto che la mancanza della possibilità di composizione delle reti è una seria limitazione di Petri poiché è limitata la modularità. In aggiunta, Hewitt ha sostenuto che le reti di Petri mancano di località poiché i token di input di una transizione scompaiono simultaneamente, cosa che limita il realismo del modello.^[10] Hewitt conosceva l'immediata contro-risposta alla sua osservazione, cioè che l'uso proprio delle reti di Petri è obbedire al vincolo del singolo evento, ogni transizione dovrebbe modellare un singolo evento. Ma senza tenere conto del tempo necessario perché l'evento accada o del tempo necessario affinché l'operazione associata alla transazione sia compiuta. forma ${\displaystyle PN=(N,M,W)}$ , che estende la rete elementare in modo che:

1. ${\displaystyle N=(P,T,F)}$ è una rete.
2. ${\displaystyle M:P\rightarrow Z}$ è un multiinsieme.
3. ${\displaystyle W:F\rightarrow Z}$ è un multiinsieme di archi.

Semantica

Un grafo di rete di Petri è una quadrupla ${\displaystyle (S,T,F,W)}$ , dove:

• ${\displaystyle S}$ è un insieme finito di posti
• ${\displaystyle T}$ è un insieme finito di transizioni, con ${\displaystyle S\cap T=\varnothing }$
• ${\displaystyle F:(S\times T)\cup (T\times S)\to \mathbb {N} }$ è un multiinsieme di archi (relazione di flusso)
• ${\displaystyle W:F\rightarrow \mathbb {N} \backslash \lbrace 0\rbrace }$ è la funzione di peso di un arco

La relazione di flusso è un insieme di archi ${\displaystyle F=\{(x,y)\mid W(x,y)>0\}}$ . In molti testi, gli archi possono avere molteplicità 1. Useremo la convenzione di usare ${\displaystyle F}$ al posto di ${\displaystyle W}$ ottenendo così che un grafo di rete di Petri è un multigrafo bipartito ${\displaystyle (S\cup T,F)}$.

Il pre-insieme di una transizione ${\displaystyle t}$, è l'insieme dei suoi posti di input: ${\displaystyle ^{\bullet }t=\{s\in S\mid W(s,t)>0\}}$ ; il post-insieme è un insieme dei posti di output: ${\displaystyle t{}^{\bullet }=\{s\in S\mid W(t,s)>0\}}$. Le due definizione sono analoghe.

Una marcatura di una rete di Petri è un multiinsieme dei suoi posti, cioè una mappatura ${\displaystyle M:S\to \mathbb {N} }$ . Diremo quindi che la marcatura assegna un numero di token.

Una rete di Petri è una quartupla ${\displaystyle (S,T,W,M_{0})}$, dove:

• ${\displaystyle (S,T,W)}$ è un grafo di rete di Petri;
• ${\displaystyle M_{0}}$ è la marcatura iniziale.

Semantica di esecuzione

Il comportamento di una rete di Petri viene definito attraverso relazioni fra le marcature, da notare che la marcatura può essere aggiunta come un qualsiasi multiinsieme: ${\displaystyle M+M'\ {\stackrel {D}{=}}\ \{s\to M(s)+M'(s)\mid s\in S\}}$

L'esecuzione di un grafo di rete di Petri ${\displaystyle G=(S,T,W)}$ può essere definito attraverso la relazione di transizione ${\displaystyle \to _{G}}$ sulle marcature, nel modo seguente:

• per ogni t in ${\displaystyle T:M\to _{G,t}M'\ {\stackrel {D}{\Leftrightarrow }}\ \exists M'':S\to \mathbb {N} :M=M''+{\textstyle \sum _{s\in S}W(s,t)\ \wedge \ M'=M''+{\textstyle \sum _{s\in S}W(t,s)}}}$
• ${\displaystyle M\to _{G}M'\ {\stackrel {D}{\Leftrightarrow }}\ \exists t\in T:M\to _{G,t}M'}$

In parole:

• Far scattare una transizione ${\displaystyle t}$ in una marcatura ${\displaystyle M}$ consuma ${\displaystyle W(s,t)}$ token da ognuno dei posti in input ${\displaystyle s}$ di ${\displaystyle t}$, e produce ${\displaystyle W(t,s)}$ token per ognuno dei posti output ${\displaystyle s}$ di ${\displaystyle t}$.
• Una transizione è abilitata (potrebbe scattare) se ci sono abbastanza token nei suoi posti input per rendere possibile il consumo di essi, vale a dire se e solo se ${\displaystyle \forall s:M(s)\geq W(s,t)}$ .

Siamo generalmente interessati a cosa potrebbe accadere nel caso in cui le transizioni scattassero in ordine arbitrario. Diciamo che una marcatura ${\displaystyle M'}$ è raggiungibile da una marcatura ${\displaystyle M}$ in un solo passo se ${\displaystyle M\to _{G}M'}$, diciamo inoltre che è raggiungibile da ${\displaystyle M}$ se ${\displaystyle M\to _{G}^{*}M'}$ , dove ${\displaystyle \to _{G}^{*}}$ è la chiusura riflessiva e transitiva di ${\displaystyle \to _{G}}$ se è raggiungibile in 0 o più passi.

Per una rete di Petri (marcata) ${\displaystyle N=(S,T,W,M_{0})}$ , siamo interessati agli scatti che possono essere compiuti partendo dalla marcatura iniziale ${\displaystyle M_{0}}$ . Definiamo l'insieme di marcature raggiungibili come: ${\displaystyle R(N)\ {\stackrel {D}{=}}\ \{M'\mid M_{0}\to _{(S,T,W)}^{*}M'\}}$

Il grafo di raggiungibilità di N è la relazione di transizione ${\displaystyle \to _{G}}$ ristretta alle marcature raggiungibili ${\displaystyle R(N)}$ .

Una sequenza di scatti per una rete di Petri, un grafo G e una marcatura iniziale ${\displaystyle M_{0}}$ è una sequenza di transizioni ${\displaystyle {\vec {\sigma }}=\langle t_{i_{1}}\ldots t_{i_{n}}\rangle }$ tale che ${\displaystyle M_{0}\to _{G,t_{i_{1}}}M_{1}\wedge \ldots \wedge M_{n-1}\to _{G,t_{i_{n}}}M_{n}}$ . L'insieme delle sequenze di scatti denotato da ${\displaystyle L(N)}$ .

Reti di Petri come vettori e matrici

La marcatura per le reti di Petri ${\displaystyle (S,T,W,M_{0})}$ può essere apprezzato meglio sotto forma di vettore di interi non negativi di lunghezza ${\displaystyle |S|}$ .

La relazione di transizione può essere descritta da una coppia di matrici di dimensioni ${\displaystyle |S|\times |T|}$ :

• ${\displaystyle W^{-}}$ definito da ${\displaystyle \forall s,t:W^{-}[s,t]=W(s,t)}$
• ${\displaystyle W^{+}}$ definito da ${\displaystyle \forall s,t:W^{+}[s,t]=W(t,s)}$

Allora la loro differenza:

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

può essere usato per descrivere la marcatura raggiungibile in termini di prodotto tra matrici nel modo seguente:

Per ogni sequenza di transizioni ${\displaystyle w}$ , scriviamo ${\displaystyle o(w)}$ per il vettore che mappa ogni transizione al suo numero di occorrenza in w. Allora, abbiamo:

${\displaystyle R(N)=\{M\mid \exists w:M=M_{0}+W^{T}\cdot o(w)\wedge w\;{\grave {e}}\;una\;sequenza\;di\;scatto\;di\;N\}}$

Da notare che è richiesto che ${\displaystyle w}$ sia una frequenza di scatto, permettere sequenze di transizioni senza vincoli generalmente produce un insieme molto grande.

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

Raggiungibilità

Tutti gli stati che possono essere raggiunti da una rete ${\displaystyle N}$ con marcatura iniziale ${\displaystyle M_{0}}$ sono indicati con ${\displaystyle R(N,M_{0})}$. Il problema della raggiungibilità è il seguente: è vero che ${\displaystyle M_{w}\in R(N,M_{0})}$? Ovvero in quali casi ${\displaystyle M_{w}}$ è uno stato "sbagliato", che non deve essere raggiunto, ad esempio il passaggio di un treno quando la sbarra del passaggio a livello è alzata, o la salita di un ascensore quando le porte sono aperte.

La raggiungibilità degli stati può essere rappresentata con un grafo di raggiungibilità ove sono indicati gli stati e gli archi rappresentano le transizioni tra due stati. Il grafo è costruito come segue: si considera per primo lo stato di partenza (${\displaystyle M_{0}}$) e vengono esplorate tutte le possibili transizioni da questo stato, poi le transizioni dagli stati trovati e così via. L'algoritmo con cui è costruito il grafo è quello di ricerca breadth-first, poiché il grafo può avere larghezza infinita, quindi una ricerca depth-first potrebbe non trovare tutti i possibili stati, anche se eseguito un numero infinito di volte. Si nota che la rete di Petri è intrinsecamente limitata (vedi appresso) se e solo se il suo grafo di raggiungibilità ha un numero finito di stati.

Mentre la raggiungibilità sembra essere un buon metodo per trovare gli stati "sbagliati", per problemi pratici il grafo costruito ha di solito troppi stati da calcolare. Per alleggerire questo problema, è usata spesso la logica temporale lineare (LTL) in congiunzione con il metodo tableau per provare che certi stati non possono essere raggiunti. LTL usa la tecnica della semi-decisione per trovare se davvero uno stato può essere raggiunto, ricercando un insieme di condizioni necessarie affinché lo stato sia raggiunto e provando che tali condizioni non possono essere soddisfatte.

Liveness

Una rete di Petri è viva o live se, qualunque sia la marcatura ${\displaystyle m}$ raggiunta a partire da ${\displaystyle m_{0}}$, da ${\displaystyle m}$ è sempre possibile far scattare qualunque transizione della rete a seguito di un'ulteriore sequenza di scatti.

Sono definiti diversi livelli di liveness (in letteratura anche vivezza o vitalità), da ${\displaystyle L_{0}}$ a ${\displaystyle L_{4}}$. Una transizione t di una rete di Petri (${\displaystyle N,M_{0}}$) può essere:^[11]

• ${\displaystyle L_{0}}$ live, o morta se e solo se essa non può scattare, cioè se non è in nessuna sequenza di scatto ${\displaystyle {\vec {\sigma }}}$ dove ${\displaystyle {\vec {\sigma }}\in L(N,M_{0})}$
• ${\displaystyle L_{1}}$ live, o quasi-viva, se e solo se essa ha la possibilità di scattare, cioè se si trova in una sequenza di scatto ${\displaystyle {\vec {\sigma }}}$ ove ${\displaystyle {\vec {\sigma }}\in L(N,M_{0})}$
• ${\displaystyle L_{2}}$ live se e solo se per ogni k intero positivo, t può scattare almeno k volte in una sequenza di scatto ${\displaystyle {\vec {\sigma }}}$ ove ${\displaystyle {\vec {\sigma }}\in L(N,M_{0})}$
• ${\displaystyle L_{3}}$ live se e solo se esiste una sequenza di scatto ${\displaystyle {\vec {\sigma }}\in L(N,M_{0})}$ dove t scatta all'infinito
• ${\displaystyle L_{4}}$ live o semplicemente live se e solo se in ogni stato raggiungibile M (cioè ${\displaystyle \forall M\in R(N,M_{0})}$), t è ${\displaystyle L_{1}}$ viva.

Si nota che questi sono requisiti sempre più stringenti, ad esempio se una transizione è ${\displaystyle L_{3}}$ live, essa è automaticamente ${\displaystyle L_{1}}$ ed ${\displaystyle L_{2}}$ live. Come esempi, (b) mostra una rete di Petri viva con un dato stato iniziale, ma con un altro stato iniziale (per esempio totalmente vuoto) tutte le transizioni possono essere morte. Dall'altra parte, (a) mostra transizioni di una rete di Petri tutte ${\displaystyle L_{3}}$ live non importa cosa sia lo stato iniziale - esse non sono ${\displaystyle L_{4}}$ live, poiché quando lo stato è (0,2) oppure (2,0), una delle sue transizioni può non scattare in quanto la rete è 2-bounded.

Una rete di Petri è ${\displaystyle L_{k}}$ live se e solo se ogni transizione con essa è ${\displaystyle L_{k}}$ live.

Limitatezza

Ci sono delle reti di Petri in cui il numero massimo di token contenuti in un posto è limitato - in questo caso, la limitatezza è una proprietà intrinseca della rete. Comunque, le reti di Petri possono essere definite senza avere la proprietà della limitatezza; allora la limitatezza è una possibile proprietà della rete di Petri. Una rete di Petri si dice k-limitata se esiste un numero intero positivo k (finito) tale che il numero di token in ogni posto della rete è minore o uguale a k per ogni marcatura raggiungibile da ${\displaystyle M_{0}}$ Una rete di Petri è sicura o safe se è 1-limitata. Naturalmente, la limitatezza dipende dalla marcatura dello stato iniziale ${\displaystyle M_{0}}$ (cioè possiamo mettere 10 token in ogni posto inizialmente, rendendo impossibile avere una rete 2-limitata). Si nota inoltre che l'esempio (b) non è limitata poiché P4 può possedere un numero infinito di token, se la sequenza di scatto (T1,T2) si ripete all'infinito. Comunque, la rete dell'esempio (a) è intrinsecamente k-limitata per k=2 in tutti i posti e ciò è mostrato in tutti i possibili stati.

La limitatezza di un particolare posto in una rete limitata intrinsecamente può essere rappresentata in modo equivalente con una rete non espressamente limitata mediante una "trasformazione di posto", ovvero inserendo un nuovo posto (chiamato counter-place, posto di conteggio) e facendo sì che tutte le transizioni che mettono x token nel posto originale prendano x token dal posto di conteggio, e tutte le transizioni che portano via x token dal posto originale mettano poi x token nel posto di conteggio. Il numero di token in ${\displaystyle M_{0}}$ dovranno adesso soddisfare l'equazione posto + posto di conteggio = limitatezza. Quindi, facendo una trasformazione di posto per tutti i posti nella rete limitata e costringendo lo stato di partenza ${\displaystyle M_{0}}$ ad adeguarsi alla suddetta eguaglianza, una rete limitata può semplicemente essere trasformata in una rete non limitata. Quindi un'analisi utilizzata per una rete intrinsecamente non-limitata può essere usata anche per le reti limitate.

P-invariante

I P-invarianti corrispondono ad un insieme di posti tale che la somma pesata dei gettoni che la contengono rimane costante per tutte le marcature raggiungibili dalla rete. Dato ${\displaystyle C}$ matrice di incidenza della rete di Petri e ${\displaystyle x}$ vettore colonna di dimensione |P|, i P-invarianti sono le soluzioni intere della seguente equazione: ${\displaystyle x^{T}C=0}$

Dove, per esempio per una rete di Petri avente 5 posti, abbiamo il seguente vettore ${\displaystyle x^{T}=[x_{1},x_{2},x_{3},x_{4},x_{5}]}$

T-invariante

In modo duale ai P-invarianti, i T-invarianti rappresentano possibili sequenze di scatti che riportano la rete alla marcatura iniziale. Dato ${\displaystyle C}$ matrice di incidenza della rete di Petri e ${\displaystyle y}$ vettore colonna di dimensione |T|, i T-invarianti sono le soluzioni intere della seguente equazione: ${\displaystyle Cy=0}$

Sifoni e trappole

Sono delle strutture fondamentali per riconoscere la vivezza di una rete di Petri.

Sifoni

Un sifone, è un insieme di posti che, durante l'evoluzione della rete, tende a perdere gettoni e non è più capace di acquistarne di nuovi. Dato S un insieme di posti della rete di Petri, il sifone è definito: ${\displaystyle \bullet S\subseteq S\bullet }$

Trappole

Sono il duale dei sifoni, è un insieme di posti che, durante l'evoluzione della rete, tende ad acquisire gettoni e non è più in grado di smarcarsi completamente. Dato S un insieme di posti della rete di Petri, la trappola è definita: ${\displaystyle S\bullet \subseteq \bullet S}$

Aree di applicazione

• Calcolo differenziale booleano^[12]
• Business process modeling^[13][14]
• Biologia computazionale^[15][16]
• Programmazione concorrente^[17]
• Ingegneria dell'automazione^[18][19][20]
• Analisi dei dati^[21]
• Diagnostica (intelligenza artificiale)^[22]
• Controllo di processo discreto^[23][24][25]
• Teoria dei giochi^[26]
• Progettazione hardware^[27][28][29]
• Reti di processo di Kahn^[30]
• Modellazione dei processi^[31][32][33]
• Ingegneria dell'affidabilità^[34][35]
• Simulazione^[13]
• Software design^[36]
• Workflow management system^[32][33][37]

Note

Bibliografia

• (EN) Janette Cardoso e Heloisa Camargo, Fuzziness in Petri Nets, Physica-Verlag, 1999, ISBN 978-3-7908-1158-2.
• (EN) Manuel Chiachio, Juan Chiachio, Darren Presscott e John Andrews, A new paradigm for uncertain knowledge representation by Plausible Petri nets, in Information Sciences, vol. 453, luglio 2018, pp. 323-345, DOI:10.1016/j.ins.2018.04.029.
• (EN) Iwona Grobelna, Formal verification of embedded logic controller specification with computer deduction in temporal logic (PDF), in Przegląd Elektrotechniczny, vol. 87, 12a, 2011, pp. 47-50.
• (EN) Kurt Jensen, Coloured Petri Nets, Springer Verlag, 1997, ISBN 978-3-540-62867-5.
• (HU) András Pataricza, Formális moódszerek az informatikában, TYPOTEX Kiadó, 2004, ISBN 978-963-9548-08-4.
• (EN) James Lyle Peterson, Petri Nets, in ACM Computing Surveys, vol. 9, n. 3, 1977, pp. 223-252, DOI:10.1145/356698.356702.
• (EN) James Lyle Peterson, Petri Net Theory and the Modeling of Systems, Prentice Hall, 1981, ISBN 978-0-13-661983-3.
• (DE) Carl Adam Petri, Kommunikation mit Automaten (PDF) (Ph.D. Thesis), Università di Bonn, 1962.
• Wolfgang Reisig, Le reti di Petri, Arnoldo Mondadori Editore, 1984, OCLC 797058669.
• (EN) Wolfgang Reisig, A Primer in Petri Net Design, Springer-Verlag, 1992, ISBN 978-3-540-52044-3.
• (EN) Robert-Christoph Riemann, Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus, Herbert Utz Verlag, 1999, ISBN 978-3-89675-629-9.
• (EN) Harald Störrle, Models of Software Architecture - Design and Analysis with UML and Petri-Nets, H. Störrle, 2000, ISBN 978-3-8311-1330-9.
• (EN) Dmitry Zaitsev, Clans of Petri Nets: Verification of protocols and performance evaluation of networks, LAP LAMBERT Academic Publishing, 2013, ISBN 978-3-659-42228-7.
• (EN) Mengchu Zhou e Frank Dicesare, Petri Net Synthesis for Discrete Event Control of Manufacturing Systems, Kluwer Academic Publishers, 1993, ISBN 978-0-7923-9289-7.
• (EN) Mengchu Zhou e Kurapati Venkatesh, Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach, World Scientific Publishing, 1999, ISBN 978-981-02-3029-6.
• (EN) Xu Xue-Guo, Picture Fuzzy Petri Nets for Knowledge Representation and Acquisition in Considering Conflicting Opinions, in Applied Sciences, vol. 9, n. 5, 2019, p. 983, DOI:10.3390/app9050983.

Altri progetti

• Wikimedia Commons contiene immagini o altri file sulla rete di Petri

Collegamenti esterni

• Mauro Cappelli, rete di Petri, in Enciclopedia della scienza e della tecnica, Istituto dell'Enciclopedia Italiana, 2007-2008.
• (EN) Opere riguardanti Petri nets, su Open Library, Internet Archive.
• (EN) Petri net, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL
• (EN) Petri Nets World, su informatik.uni-hamburg.de, Università di Amburgo. URL consultato il 26 maggio 2024.
• (EN) XRL (eXchangeable Routing Language), su is.tm.tue.nl, Università tecnica di Eindhoven (archiviato dall'url originale il 22 marzo 2007).

Controllo di autorità	Thesaurus BNCF 6134 · LCCN (EN) sh85100346 · GND (DE) 4045388-1 · BNE (ES) XX548185 (data) · J9U (EN, HE) 987007538726205171