Rete di Petri: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
aggiunta p-invariante, t-invariante, sifoni e trappole |
Aggiungi 1 libro per la Wikipedia:Verificabilità (20250910)) #IABot (v2.0.9.5) (GreenC bot |
||
| (75 versioni intermedie di 47 utenti non mostrate) | |||
Riga 1:
[[
Una '''rete di
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.<ref>{{Cita pubblicazione|autore=Alessandro Giua|autore2=Manuel Silva|titolo=Petri nets and Automatic Control: A historical perspective|lingua=en|pubblicazione=Annual Reviews in Control|volume=45|numero=2|pp=223-239|anno=2018|url=https://www.alessandro-giua.it/UNICA/PAPERS/JOUR/18arc_draft.pdf|doi=10.1016/j.arcontrol.2018.04.006}}</ref><ref>{{Cita pubblicazione|autore=Carl Adam Petri|titolo=Speech - Gold Medal of Honor, The Academy of Transdisciplinary Learning and Advanced Studies (ATLAS)|lingua=en|editore=Università di Amburgo|anno=2007|url=https://www.informatik.uni-hamburg.de/TGI/mitarbeiter/profs/petri/Antalya.pdf}}</ref><ref>{{Cita pubblicazione|titolo=Obituary - Carl Adam Petri (1926-2010)|lingua=en|editore=Università di Amburgo|url=https://www.inf.uni-hamburg.de/home/about/honors/petri.pdf}}</ref>
== Descrizione ==
=== Concetti base ===
Una rete di Petri PT (Place/Transition) è un [[grafo orientato]] con due tipi di nodi, '''posti''' e '''transizioni''', connessi da archi orientati. I posti sono rappresentati graficamente da cerchi e le transizioni da rettangoli.
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''' (
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 determinismo|non deterministica]]. Ciò significa due cose:
Riga 15 ⟶ 17:
Poiché lo scatto di una transizione non è predicibile a priori, le reti di Petri sono molto adatte a modellare il comportamento di un sistema [[Concorrenza (informatica)|concorrente]].
===
Una rete di Petri è un [[sistema a transizione di stati]] che estende una classe di reti, dette reti elementari.<ref>{{Cita libro|autore=Grzegorz Rozenberg|autore2=Joost Engelfriet|capitolo=Elementary Net Systems|titolo=Lectures on Petri Nets I: Basic Models – Advances in Petri Nets|url=https://archive.org/details/lecturesonpetrin1491unse|lingua=en|volume=1491|collana=Lecture Notes in Computer Science|editore=Springer|anno=1998|pp=[https://archive.org/details/lecturesonpetrin1491unse/page/n25 12]-121|isbn=3-540-65306-6|doi=10.1007/3-540-65306-6_14}}</ref>
'''Definizione 1''': Una '''rete''' è una tripla <math>N=(P,T,F)</math> dove:
# <math>P</math> è un insieme di stati chiamati posti.
Riga 25 ⟶ 26:
# <math>F\subset(P\times T)\bigcup(T\times P)</math> è un insieme di flussi relazionali chiamati “archi”. Tali flussi sono possibili solamente tra posti e transizioni o viceversa.
Una rete è un grafo bipartito, dove <math>P</math> è una partizione e <math>T</math> è l'altra. Più precisamente, per ogni <math>t</math> in <math>T</math> esistono <math>p</math> e <math>q</math> in <math>P</math> tali che <math>(p,t)</math> e <math>(t,q)</math> appartengono ad <math>F</math> e per ogni <math>p</math> e <math>q</math> in <math>P</math> se <math>(p, t)</math> e <math>(t, q)</math> sono in <math>F</math> allora <math>p \neq
<math>\forall t\in T\,\,\exists p,q\in P\,\, t.c.\,\,(p,t),(t,q)\in F\, p\neq q </math>
L'insieme <math>P\bigcup T</math>
'''Definizione 2''': Data una rete <math>N=(P,T,F)</math> , una '''configurazione''' è un insieme <math>C\subseteq P</math>.
'''Definizione 3''': Una '''rete elementare''' è una rete della forma <math>EN=(N,C)</math>
# <math>N=(P,T,F)</math>
# <math>C\subseteq P</math>
'''Definizione 4''': Una '''rete di Petri''' è una rete della
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 ===
[[File:Petri net types.svg|thumb|I principali tipi di reti di Petri.]]
Ci sono sei tipi principali delle reti di Petri:
# [[Automa a stati finiti|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: <math>\forall t\in T: |t\bullet|=|\bullet t|=1</math>
# [[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: <math>\forall p\in P: |p\bullet|=|\bullet p|=1</math>
# [[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: <math>\forall p\in P: (|p\bullet|\leq 1) \vee (\bullet (p\bullet)=\{p\})</math>
# [[Scelta libera estesa]] (Extended free choice - EFC) - una rete di Petri che può essere ''trasformata in una FC''.
# [[Scelta asimmetrica]] (Asymmetric choice - AC) - concorrenza e conflitto (insomma, ''confusion''), ma ''non asimmetricamente''. Matematicamente: <math>\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)]</math>
=== 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.<ref>{{Cita libro|autore=Kurt Jensen|titolo=A brief introduction to colored Petri nets|url=https://archive.org/details/toolsalgorithmsf1217taca|lingua=en|volume=1217|pp=[https://archive.org/details/toolsalgorithmsf1217taca/page/203 203]-208|doi=10.1007/BFb0035389|capitolo=A brief introduction to coloured Petri Nets|collana=Lecture Notes in Computer Science|anno=1997|isbn=978-3-540-62790-6}}</ref> 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.<ref>{{Cita web|url=http://www.daimi.au.dk/CPnets/intro/verybrief.html|titolo=Very Brief Introduction to CP-nets|lingua=en|editore=Università di Aarhus|urlarchivio=https://web.archive.org/web/20101028221803/http://www.daimi.au.dk/CPnets/intro/verybrief.html}}</ref> 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 [[Hermann von Fehling|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.<ref>{{Cita web|url=http://www.llpn.com/OPNs.html|titolo=What are Object Petri Nets?|sito=LLPN - Linear Logic Petri Nets|lingua=en|urlarchivio=https://web.archive.org/web/20051103131745/http://www.llpn.com/OPNs.html}}</ref>
* 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 [[Variabile casuale esponenziale negativa|distribuzione casuale esponenziale]] è tipicamente utilizzata per "tempificare" tali reti. In questo caso, il grafo di raggiungibilità della rete diventa una [[processo markoviano|catena di Markov]].
* Le [[reti di Petri dualistiche]] (dP-Nets) sono un'estensione delle reti di Petri sviluppata da E. Dawis ''et al.''<ref>{{Cita pubblicazione|autore=E.P. Dawis|autore2=J. F. Dawis|autore3=Wei-Pin Koo|anno=2001|titolo=Architecture of Computer-based Systems using Dualistic Petri Nets|pubblicazione=2001 IEEE International Conference on Systems, Man, and Cybernetics|lingua=en|volume=3|pp=1554-1558|isbn=0-7803-7087-2|doi=10.1109/ICSMC.2001.973505}}</ref> 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]],<ref>{{Cita pubblicazione|autore=E. P. Dawis|anno= 2001|titolo=Architecture of an SS7 Protocol Stack on a Broadband Switch Platform using Dualistic Petri Nets|pubblicazione=2001 IEEE Pacific Rim Conference on Communications, Computers and signal Processing|lingua=en|volume=1|pp=323-326|doi=10.1109/PACRIM.2001.953588|isbn=0-7803-7080-5 }}</ref> 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 [[comunicazione a scambio di messaggi|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.<ref>{{Cita pubblicazione|url=https://arxiv.org/vc/arxiv/papers/1008/1008.1459v8.pdf|autore=Carl Hewitt|titolo=Actor Model of Computation|data=7 novembre 2010|lingua=en}}</ref> 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 <math>PN=(N,M,W)</math> , che estende la rete elementare in modo che:
# <math>N=(P,T,F)</math> è una rete.
# <math>M:P\rightarrow Z</math> è un [[multiinsieme]].
# <math>W:F\rightarrow Z</math> è un multiinsieme di archi.
== Semantica ==
Un '''grafo di rete di Petri''' è una
*<math>S</math>
*<math>T</math>
*<math>F:(S\times T)\cup(T\times S)\to\mathbb{N}</math> è un multiinsieme di archi (relazione di flusso)
*<math>W:
La relazione di flusso è un insieme di archi <math>F=\{(x,y)\mid W(x,y)>0\}</math> . In molti testi, gli archi possono avere molteplicità 1. Useremo la convenzione di usare <math>F</math> al posto di <math>W</math> ottenendo così che un grafo di rete di Petri è un [[multigrafo]] bipartito <math>(S\cup T,F)</math>.
Il pre-insieme di una transizione <math>t</math>, è l'insieme dei suoi posti di input: <math>^{\bullet}t=\{s\in S\mid W(s,t)>0\}</math> ; il post-insieme è un insieme dei posti di output: <math>t{}^{\bullet}=\{s\in S\mid W(t,s)>0\}</math>. Le due
Una marcatura di una rete di Petri è un multiinsieme dei suoi posti, cioè una mappatura <math>M:S\to\mathbb{N}</math> . Diremo quindi che la marcatura assegna un numero di token.
Riga 63 ⟶ 97:
*<math>M_{0}</math> è la marcatura iniziale.
=== Semantica di
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: <math>M+M'\ \stackrel{D}{=}\ \{s\to M(s)+M'(s)\mid s\in S\}</math>
L'esecuzione di un grafo di rete di Petri <math>G=(S,T,W)</math>
* per ogni t in <math>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)}}</math>
* <math>M\to_{G}M'\ \stackrel{D}{\Leftrightarrow}\ \exists t\in T:M\to_{G,t}M '</math>
In parole:
* Far scattare una transizione <math>t</math> in una marcatura <math>M</math> consuma <math>W(s,t)</math>
* 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 <math>\forall s:M(s)\geq W(s,t)</math> .
Siamo generalmente interessati a cosa potrebbe accadere
Per una rete di Petri (marcata) <math>N=(S,T,W,M_{0})</math> , siamo interessati agli scatti che possono essere compiuti partendo dalla marcatura iniziale <math>M_{0}</math> . Definiamo l'insieme di marcature raggiungibili come: <math>R(N)\ \stackrel{D}{=}\ \{M'\mid M_{0}\to_{(S,T,W)}^{*}M'\} </math>
Il grafo di raggiungibilità di N è la relazione di transizione <math>\to_{G}</math>
Una sequenza di scatti per una rete di Petri, un grafo G e una marcatura iniziale <math>M_{0}</math> è una sequenza di transizioni <math>\vec{\sigma}=\langle t_{i_{1}}\ldots t_{i_{n}}\rangle</math> tale che <math>M_{0}\to_{G,t_{i_{1}}}M_{1}\wedge\ldots\wedge M_{n-1}\to_{G,t_{i_{n}}}M_{n}</math> . L'insieme delle sequenze di scatti denotato da <math>L(N)</math> .
== Reti di Petri come vettori e matrici ==
La marcatura per le reti di Petri <math>(S,T,W,M_{0})</math> può essere apprezzato meglio sotto forma di vettore di interi non negativi di lunghezza <math>|S|</math> .
La relazione di transizione può essere descritta da una coppia di matrici di dimensioni <math>|S|\times|T|</math> :
*<math>W^{-}</math>
*<math>W^{+}</math>
Allora la loro differenza:
Riga 99 ⟶ 130:
può essere usato per descrivere la marcatura raggiungibile in termini di prodotto tra matrici nel modo seguente:
Per ogni sequenza di transizioni <math>w</math> , scriviamo <math>o(w)</math>
<math>R(N)=\{M\mid\exists w:M=M_{0}+W^{T}\cdot o(w)\wedge w\;\grave{e}\; una\; sequenza\; di\; scatto\; di\; N\}</math>
Da notare che è richiesto che <math>w</math> sia una frequenza di scatto, permettere sequenze di transizioni senza vincoli generalmente produce un insieme molto grande.
[[File:detailed petri net.png|frame|(b) Esempio di una rete di Petri]]
<math>W^{+}=\begin{bmatrix} * & t1 & t2 \\ p1 & 0 & 1 \\ p2 & 1 & 0 \\ p3 & 1& 0 \\ p4 & 0 & 1 \end{bmatrix} </math> <math> W^{-}=\begin{bmatrix} * & t1 & t2 \\ p1 & 1 & 0 \\ p2 & 0 & 1 \\ p3 & 0 & 1 \\ p4 & 0 & 0 \end{bmatrix} </math> <math>W^{T}=\begin{bmatrix} * & t1 & t2 \\ p1 & -1 & 1 \\ p2 & 1 & -1 \\ p3 & 1 & -1 \\ p4 & 0 & 1 \end{bmatrix}</math> <math>M_{0}=\begin{bmatrix} 1 & 0 & 2 & 1 \end{bmatrix}</math>
=== Raggiungibilità ===
[[File:Reachability graph for petri net.png|left|frame|Grafo di raggiungibilità della rete dell'esempio (a). Si nota che la rete è 2-bounded e quindi può avere solo un massimo di 9 (<math>3^2</math>) stati.]]
Tutti gli stati che possono essere raggiunti da una rete <math>N</math> con marcatura iniziale <math>M_{0}</math> sono indicati con <math>R(N,M_{0})</math>. Il ''problema della raggiungibilità'' è il seguente: è vero che <math>M_{w} \in
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 (<math>M_0</math>) 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.
Riga 119 ⟶ 151:
=== Liveness ===
Una rete di Petri è ''viva'' o ''live'' se, qualunque sia la marcatura <math>m</math> raggiunta a partire da <math>m_0</math>, da <math>m</math> è sempre possibile far scattare qualunque transizione della rete a seguito di
Sono definiti diversi livelli di ''liveness'' (in letteratura anche ''vivezza'' o ''vitalità''), da <math>L_0</math> a <math>L_4</math>. Una transizione ''t'' di una rete di Petri (<math>N,M_0</math>) può essere:<ref>{{Cita pubblicazione|url=https://inst.eecs.berkeley.edu/~ee249/fa07/discussions/PetriNets-Murata.pdf|autore=Tadao Murata|titolo=Petri Nets: Properties, Analysis and Applications|lingua=en|pubblicazione=Proceedings of the IEEE|volume=77|numero=4|pp=541-558|data=aprile 1989|doi=10.1109/5.24143}}</ref>
* <math>L_0</math> ''live'', o ''morta'' [[se e solo se]] essa non può scattare, cioè se non è in nessuna sequenza di scatto <math>\vec \sigma</math> dove <math>\vec \sigma \in L(N,M_0)</math>
* <math>L_1</math> ''live'', o ''quasi-viva'', se e solo se essa ha la possibilità di scattare, cioè se si trova in una sequenza di scatto <math>\vec \sigma</math> ove <math>\vec \sigma \in L(N,M_0)</math>
* <math>L_2</math> ''live'' se e solo se per ogni k intero positivo, t può scattare almeno k volte in una sequenza di scatto <math>\vec \sigma</math> ove <math>\vec \sigma \in L(N,M_0)</math>
Riga 129 ⟶ 160:
* <math>L_4</math> ''live'' o semplicemente ''live'' se e solo se in ogni stato raggiungibile M (cioè <math>\forall M \in R(N,M_0)</math>), ''t'' è <math>L_1</math> viva.
Si nota che questi sono requisiti sempre più stringenti, ad esempio se una transizione è <math>L_3</math> ''live'', essa è automaticamente <math>L_1</math> ed <math>L_2</math> ''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
Una rete di Petri è <math>L_k</math> ''live'' se e solo se ogni transizione con essa è <math>L_k</math> ''live''.
===
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 ''
Una rete di Petri si dice '''k-
Una rete di Petri è ''sicura'' o ''safe'' se è 1-
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-
[[
La ''
=== 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 <math>C</math> matrice di incidenza della rete di Petri e <math>x</math> vettore colonna di dimensione |P|, i P-invarianti sono le soluzioni intere della seguente equazione:
Riga 150 ⟶ 181:
Dove, per esempio per una rete di Petri avente 5 posti, abbiamo il seguente vettore <math>x^T = [x_1, x_2, x_3, x_4, x_5]</math>
=== T-invariante ===
In modo duale ai P-invarianti, i T-invarianti rappresentano possibili sequenze di scatti che riportano la rete alla marcatura iniziale.
Dato <math>C</math> matrice di incidenza della rete di Petri e <math>y</math> vettore colonna di dimensione |T|, i T-invarianti sono le soluzioni intere della seguente equazione:
<math> Cy=0 </math>
== Sifoni e
Sono delle strutture fondamentali per riconoscere la vivezza di una rete di Petri.
Riga 165 ⟶ 196:
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: <math> S \bullet \subseteq \bullet S </math>
== Aree di applicazione ==
* [[Algebra di Boole|Calcolo differenziale booleano]]<ref name="Scheuring_Wehlan_1991_Petri">{{Cita pubblicazione|titolo=Der Boolesche Differentialkalkül – Eine Methode zur Analyse und Synthese von Petri-Netzen / The Boolean differential calculus – A method for analysis and synlhesis of Petri nets|lingua=de,en|autore=Rainer Scheuring|autore2=Herbert Wehlan|data=1º dicembre 1991|pubblicazione=At - Automatisierungstechnik - Methoden und Anwendungen der Steuerungs-, Regelungs- und Informationstechnik|editore=R. Oldenbourg Verlag|issn=0178-2312|città=Stoccarda|volume=39|numero=7|pp=226-233|doi=10.1524/auto.1991.39.112.226|url=https://www.degruyter.com/view/j/auto.1991.39.issue-1-12/auto.1991.39.112.226/auto.1991.39.112.226.xml|accesso=26 maggio 2024}}</ref>
* [[Business process modeling]]<ref name="AalstStahl2011">{{Cita libro|autore=Wil M.P. van der Aalst|autore2=Christian Stahl|titolo=Modeling Business Processes - A Petri Net-Oriented Approach|lingua=en|data=27 maggio 2011|pp=1-400|editore=MIT Press|isbn=9780262015387|url=https://direct.mit.edu/books/book/2268/Modeling-Business-ProcessesA-Petri-Net-Oriented}}</ref><ref name="AalstBPM2018">{{Cita libro|autore=Wil M.P. van der Aalst|titolo=Encyclopedia of Database Systems|lingua=en|data=2018|editore=Springer|url=https://doi.org/10.1007/978-1-4614-8265-9_1179|capitolo=Business Process Management|pp=370-374|doi=10.1007/978-1-4614-8265-9_1179|isbn=978-1-4614-8266-6}}</ref>
* [[Biologia computazionale]]<ref name="Bean 2014">{{Cita pubblicazione|autore=Daniel M. Bean|autore2=Joshua Heimbach|autore3=Lorenzo Ficorella|autore4=Gos Micklem|autore5=Stephen G. Oliver|autore6=Giorgio Favrin|titolo=esyN: Network Building, Sharing and Publishing|lingua=en|pubblicazione=PLoS One|data=2 settembre 2014|pmid=25181461|doi=10.1371/journal.pone.0106035|volume=9|numero=9|pmc=4152123|pp=e106035|bibcode=2014PLoSO...9j6035B}}</ref><ref>{{Cita libro|autore=Ina Koch|autore2=Wolfgang Reisig|autore3=Falk Schreiber|titolo=Modeling in Systems Biology - The Petri Net Approach|lingua=en|collana=Computational Biology|data=2011|volume=16|editore=Springer|doi=10.1007/978-1-84996-474-6|isbn=978-1-84996-473-9|url=https://dx.doi.org/10.1007/978-1-84996-474-6}}</ref>
* [[Programmazione concorrente]]<ref>{{Cita pubblicazione|autore=L. M. Kristensen|autore2=M. Westergaard|titolo=Formal Methods for Industrial Critical Systems|lingua=en|data=2010|capitolo=Automatic Structure-Based Code Generation from Coloured Petri Nets: A Proof of Concept|pubblicazione=Formal Methods for Industrial Critical Systems - 15th International Workshop, FMICS 2010|collana=Lecture Notes in Computer Science|volume=6371|pp=215-230|doi=10.1007/978-3-642-15898-8_14|isbn=978-3-642-15897-1}}</ref>
* [[Ingegneria dell'automazione]]<ref name="DavidAlla2005">{{Cita libro|url=https://books.google.com/books?id=VsS0JkMcXGwC|titolo=Discrete, continuous, and hybrid Petri Nets|lingua=en|autore=René David|autore2=Hassane Alla|editore=Springer|anno=2005|isbn=978-3-540-22480-8}}</ref><ref>{{Cita pubblicazione|autore=Xuehui Gao|autore2=Xinyan Hu|titolo=A Petri Net Neural Network Robust Control for New Paste Backfill Process Model|lingua=en|pubblicazione=IEEE Access|anno=2020|volume=8|pp=18420-18425|doi=10.1109/ACCESS.2020.2968510|bibcode=2020IEEEA...818420G}}</ref><ref>{{Cita pubblicazione|autore=Erik Kučera|autore2=Oto Haffner|autore3=Peter Drahoš|autore4=Roman Leskovský|autore5=Ján Cigánek|data=gennaio 2020|titolo=PetriNet Editor + PetriNet Engine: New Software Tool For Modelling and Control of Discrete Event Systems Using Petri Nets and Code Generation|lingua=en|pubblicazione=Applied Sciences|volume=10|numero=21|p=7662|doi=10.3390/app10217662}}</ref>
* [[Analisi dei dati]]<ref>{{Cita libro|autore=Wil M.P. van der Aalst|titolo=Process Mining - Data Science in Action, Second Edition|lingua=en|editore=Springer|url=https://doi.org/10.1007/978-3-662-49851-4|data=2016|doi=10.1007/978-3-662-49851-4|isbn=978-3-662-49850-7}}</ref>
* Diagnostica ([[intelligenza artificiale]])<ref>{{Cita libro|autore=J. Carmona|autore2=B.F. van Dongen|autore3=A. Solti|autore4=M. Weidlich|titolo=Conformance Checking - Relating Processes and Models|lingua=en|editore=Springer|url=https://doi.org/10.1007/978-3-319-99414-7|anno=2018|doi=10.1007/978-3-319-99414-7|isbn=978-3-319-99413-0}}</ref>
* [[Sequential function chart|Controllo di processo discreto]]<ref>{{Cita pubblicazione|autore=Joaquin L. Fernandez|autore2=Rafael Sanz|autore3=Enrique Paz|autore4=Carlos Alonso|capitolo=Using hierarchical binary Petri nets to build robust mobile robot applications: RoboGraph|lingua=en|titolo=IEEE International Conference on Robotics and Automation, 2008|pp=1372-1377|data=19-23 maggio 2008|città=Pasadena|doi=10.1109/ROBOT.2008.4543394|isbn=978-1-4244-1646-2}}</ref><ref>{{Cita pubblicazione|autore=J. Marco Mendes|autore2=Paulo Leitão|autore3=Armando W. Colombo|autore4=Francisco Restivo|titolo=High-level Petri nets for the process description and control in service-oriented manufacturing systems|lingua=en|pubblicazione=International Journal of Production Research|anno=2012|volume=50|numero=6|pp=1650-1665|url=https://doi.org/10.1080/00207543.2011.575892|editore=Taylor & Francis|doi=10.1080/00207543.2011.575892}}</ref><ref>{{Cita pubblicazione|autore=D. Fahland|autore2=C. Gierds|titolo=Active Flow and Combustion Control 2018|lingua=en|data=2013|capitolo=Analyzing and Completing Middleware Designs for Enterprise Integration Using Coloured Petri Nets|pubblicazione=Advanced Information Systems Engineering - 25th International Conference, CAiSE 2013|collana=Lecture Notes in Computer Science|volume=7908|pp=400-416|doi=10.1007/978-3-642-38709-8_26|isbn=978-3-319-98176-5}}</ref>
* [[Teoria dei giochi]]<ref>{{Cita pubblicazione|autore=Julio Clempner|titolo=Modeling shortest path games with Petri nets: a Lyapunov based theory|lingua=en|pubblicazione=International Journal of Applied Mathematics and Computer Science|anno=2006|volume=16|numero=3|pp=387-397|url=http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-amcv16i3p387bwm|issn=1641-876X}}</ref>
* [[Progettazione hardware]]<ref>{{Cita libro|data=2000|autore=Alex Yakovlev|autore2=Luis Gomes|autore3=Luciano Lavagno|titolo=Hardware Design and Petri Nets|lingua=en|url=https://doi.org/10.1007/978-1-4757-3143-9|doi=10.1007/978-1-4757-3143-9|isbn=978-1-4419-4969-1}}</ref><ref>{{Cita libro|autore=J. Cortadella|autore2=M. Kishinevsky|cognome3=A. Kondratyev|autore4=L. Lavagno|autore5=A. Yakovlev|collana=Springer Series in Advanced Microelectronics|lingua=en|anno=2002|titolo=Logic Synthesis for Asynchronous Controllers and Interfaces|url=https://doi.org/10.1007/978-3-642-55989-1|volume=8|doi=10.1007/978-3-642-55989-1|isbn=978-3-642-62776-7|issn=1437-0387}}</ref><ref>{{Cita libro|anno=2002|autore=Jordi Cortadella|autore2=Alex Yakovlev|autore3=Grzegorz Rozenberg|titolo=Concurrency and Hardware Design|lingua=en|url=https://doi.org/10.1007/3-540-36190-1|volume=2549|doi=10.1007/3-540-36190-1|isbn=978-3-540-00199-7|issn=0302-9743|collana=Lecture Notes in Computer Science}}</ref>
* [[Reti di processo di Kahn]]<ref>{{Cita pubblicazione|autore=Cinzia Bernardeschi|autore2=Nicoletta De Francesco|autore3=Gigliola Vaglini|titolo=A Petri nets semantics for data flow networks|lingua=en|pubblicazione=Acta Informatica|data=1995|volume=32|numero=4|pp=347-374|doi=10.1007/BF01178383|url=https://doi.org/10.1007/BF01178383}}</ref>
* [[Modellazione dei processi]]<ref>{{Cita libro|autore=Wil M. P. van der Aalst|autore2=Christian Stahl|autore3=Michael Westergaard|titolo=Transactions on Petri Nets and Other Models of Concurrency VII|capitolo=Strategies for Modeling Complex Processes Using Colored Petri Nets|lingua=en|pubblicazione=Trans. Petri Nets Other Model. Concurr.|collana=Lecture Notes in Computer Science|data=2013|volume=7|pp=6-55|doi=10.1007/978-3-642-38143-0_2|isbn=978-3-642-38142-3}}</ref><ref name="AalstWFpattern2018">{{Cita libro|autore=Wil M. P. van der Aalst|titolo=Encyclopedia of Database Systems|lingua=en|anno=2018|editore=Springer|url=https://doi.org/10.1007/978-1-4614-8265-9_826|capitolo=Workflow Patterns|pp=4717-4718|doi=10.1007/978-1-4614-8265-9_826|isbn=978-1-4614-8266-6}}</ref><ref name="AalstWFanalysis2018">{{Cita libro|autore=Wil M. P. van der Aalst|titolo=Encyclopedia of Database Systems|lingua=en|anno=2018|editore=Springer|url=https://doi.org/10.1007/978-1-4614-8265-9_1476|capitolo=Workflow Model Analysis|pp=4716-4717|doi=10.1007/978-1-4614-8265-9_1476|isbn=978-1-4614-8266-6}}</ref>
* [[Ingegneria dell'affidabilità]]<ref>{{Cita libro|autore=Patrick D. T. O'Connor|autore2=Andre Kleyner|titolo=Practical reliability engineering|lingua=en|anno=2012|editore=Wiley|isbn=978-1-119-96126-0|edizione=5|oclc=862121371}}</ref><ref>{{Cita pubblicazione|autore=Marion Juan|autore2=David Mailland|autore3=Nicolas Fifis|cognome4=Guy Gregoris|titolo=Modélisation des pannes d'une antenne active et modifications d'architecture|lingua=fr|pubblicazione=Techniques de l'Ingénieur|collana=Sécurité des Systèmes Industriels|data=dicembre 2021|doi=10.51257/a-v1-se1221|url=http://dx.doi.org/10.51257/a-v1-se1221}}</ref>
* [[Simulazione (informatica)|Simulazione]]<ref name="AalstStahl2011"/>
* [[Software design]]<ref>{{Cita pubblicazione|autore=Erik Kučera|cognome2=Oto Haffner|autore3=Peter Drahoš|autore4=Ján Cigánek|autore5=Roman Leskovský|autore6=Juraj Štefanovič|data=gennaio 2020|titolo=New Software Tool for Modeling and Control of Discrete-Event and Hybrid Systems Using Timed Interpreted Petri Nets|lingua=en|pubblicazione=Applied Sciences|volume=10|numero=15|p=5027|doi=10.3390/app10155027}}</ref>
* [[Workflow management system]]<ref name="AalstWFpattern2018"/><ref name="AalstWFanalysis2018"/><ref>{{Cita libro|autore=Arthur H. M. ter Hofstede|autore2=Wil M. P. van der Aalst|autore3=Michael Adams|autore4=Nick Russell|titolo=Modern Business Process Automation - YAWL and its Support Environment|lingua=en|url=https://doi.org/10.1007/978-3-642-03121-2|data=2010|doi=10.1007/978-3-642-03121-2|isbn=978-3-642-03122-9}}</ref>
== Note ==
<references/>
== Bibliografia ==
*{{Cita libro|autore=Janette Cardoso|autore2=Heloisa Camargo|anno=1999|titolo=Fuzziness in Petri Nets|editore=Physica-Verlag|lingua=en|isbn=978-3-7908-1158-2}}
*{{Cita pubblicazione|autore=Manuel Chiachio|autore2=Juan Chiachio|autore3=Darren Presscott|autore4=John Andrews|anno=2018|titolo=A new paradigm for uncertain knowledge representation by Plausible Petri nets|lingua=en|pubblicazione=Information Sciences|volume=453|data=luglio 2018|pp=323-345|doi=10.1016/j.ins.2018.04.029}}
*{{Cita pubblicazione|autore=Iwona Grobelna|titolo=Formal verification of embedded logic controller specification with computer deduction in temporal logic|lingua=en|pubblicazione=Przegląd Elektrotechniczny|anno=2011|volume=87|numero=12a|pp=47-50|url=http://pe.org.pl/articles/2011/12a/11.pdf}}
*{{Cita libro|autore=Kurt Jensen|anno=1997|titolo=Coloured Petri Nets|lingua=en|editore=Springer Verlag|isbn=978-3-540-62867-5|url=https://archive.org/details/springer_10.1007-978-3-642-60794-3}}
*{{Cita libro|autore=András Pataricza|anno=2004|titolo=Formális moódszerek az informatikában|lingua=hu|editore=TYPOTEX Kiadó|isbn=978-963-9548-08-4}}
*{{Cita pubblicazione|autore=James Lyle Peterson|titolo=Petri Nets|lingua=en|url=https://archive.org/details/sim_acm-computing-surveys_1977-09_9_3/page/223|rivista=ACM Computing Surveys|anno=1977|volume=9|numero=3|pp=223-252|doi=10.1145/356698.356702}}
*{{Cita libro|nome=James Lyle Peterson|titolo=Petri Net Theory and the Modeling of Systems|lingua=en|anno=1981|url=https://archive.org/details/petrinettheorymo0000pete|editore=Prentice Hall|isbn=978-0-13-661983-3}}
*{{Cita pubblicazione|autore=[[Carl Adam Petri]]|titolo=Kommunikation mit Automaten|lingua=de|editore=[[Università di Bonn]]|data=1962|tipo=Ph.D. Thesis|url=https://www.informatik.uni-hamburg.de/TGI/mitarbeiter/profs/petri/PetriDis.pdf}}
*{{Cita libro|autore=Wolfgang Reisig|anno=1984|titolo=Le reti di Petri|editore=Arnoldo Mondadori Editore|oclc=797058669}}
*{{Cita libro|autore=Wolfgang Reisig|anno=1992|titolo=A Primer in Petri Net Design|url=https://archive.org/details/primerinpetrinet0000reis|lingua=en|editore=Springer-Verlag|isbn=978-3-540-52044-3}}
*{{Cita libro|autore=Robert-Christoph Riemann|anno=1999|titolo=Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus|lingua=en|editore=Herbert Utz Verlag|isbn=978-3-89675-629-9}}
*{{Cita libro|autore=Harald Störrle|anno=2000|titolo=Models of Software Architecture - Design and Analysis with UML and Petri-Nets|lingua=en|editore=H. Störrle|isbn=978-3-8311-1330-9}}
*{{Cita libro|autore=Dmitry Zaitsev|anno=2013|titolo=Clans of Petri Nets: Verification of protocols and performance evaluation of networks|lingua=en|editore=LAP LAMBERT Academic Publishing|isbn=978-3-659-42228-7}}
*{{Cita libro|autore=Mengchu Zhou|autore2=Frank Dicesare|anno=1993|titolo=Petri Net Synthesis for Discrete Event Control of Manufacturing Systems|url=https://archive.org/details/petrinetsynthesi0000zhou|lingua=en|editore=Kluwer Academic Publishers|isbn=978-0-7923-9289-7}}
*{{Cita libro|autore=Mengchu Zhou|autore2=Kurapati Venkatesh|titolo=Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach|lingua=en|anno=1999|url=https://archive.org/details/modelingsimulati0000zhou|editore=World Scientific Publishing|isbn=978-981-02-3029-6}}
*{{Cita pubblicazione|autore=Xu Xue-Guo|titolo=Picture Fuzzy Petri Nets for Knowledge Representation and Acquisition in Considering Conflicting Opinions|lingua=en|pubblicazione=Applied Sciences|anno=2019|volume=9|numero=5|p=983|doi=10.3390/app9050983}}
== Altri progetti ==
{{interprogetto|
== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{FOLDOC|Petri net|Petri net}}
* {{Cita web|url=http://www.informatik.uni-hamburg.de/TGI/PetriNets/|titolo=Petri Nets World|editore=[[Università di Amburgo]]|lingua=en|accesso=26 maggio 2024}}
* {{Cita web|url=http://is.tm.tue.nl/staff/anorta/XRL/xrlHome.html|titolo=XRL (eXchangeable Routing Language)|editore=[[Università tecnica di Eindhoven]]|lingua=en|urlarchivio=https://web.archive.org/web/20070322014050/http://is.tm.tue.nl/staff/anorta/XRL/xrlHome.html}}
{{Controllo di autorità}}
{{portale|informatica|matematica}}
[[Categoria:Rete di Petri| ]]
| |||