Reti Di Petri - Classi e Principali Estensioni

download Reti Di Petri - Classi e Principali Estensioni

of 35

Transcript of Reti Di Petri - Classi e Principali Estensioni

RETI DI PETRI:CLASSI E PRINCIPALI ESTENSIONIModelli per Sistemi Distribuiti e CooperativiCorso di Laurea Magistrale in Informatica A.A. 2010-2011

Studente: Luigi Filannino Matricola: 568269

INDICE1. 2. INTRODUZIONE .......................................................................................................... 3 LE RETI DI PETRI ........................................................................................................ 4 2.1 2.2 DEFINIZIONE FORMALE DELLE RETI DI PETRI ..................................................................... 5 LE RETI POSTI/TRANSIZIONI (P/T) ................................................................................ 5

2.2.1 RAPPRESENTAZIONE GRAFICA ..................................................................................... 6 2.2.2 EVOLUZIONE DELLA RETE P/T .................................................................................... 7 2.2.3 NON DETERMINISMO ................................................................................................ 9 2.2.4 STRUTTURE MODELLISTICHE FONDAMENTALI ............................................................... 10 3. CLASSI PARTICOLARI DI RETI DI PETRI ............................................................................ 12 3.1 3.2 3.3 3.4 3.5 3.6 3.7 4. MACCHINA A STATI (STATE MACHINE SM).................................................................. 12 GRAFO MARCATO (MARKED GRAPH MG) .................................................................... 13 RETE A SCELTA LIBERA (FREE CHOICE PN FC).............................................................. 13 RETE A SCELTA LIBERA ESTESA (EXTENDED FREE CHOICE PN EFC) ................................... 15 RETE A SCELTA LIBERA ASIMMETRICA (ASYMMETRIC FREE CHOICE PN AFC) ...................... 15 RETE ORDINARIA...................................................................................................... 15 LEGAMI TRA LE VARIE TIPOLOGIE DI RETE ....................................................................... 16

ESTENSIONI DI RETI DI PETRI ....................................................................................... 16 4.1 4.2 4.3 4.4 4.5 RETI A CAPACIT LIMITATA ........................................................................................ 17 RETI CON ARCHI INIBITORI ......................................................................................... 19 RETI CON PRIORIT .................................................................................................. 20 RETI INNESTATE ....................................................................................................... 21 RETI COLORATE ....................................................................................................... 22

4.5.1 DEFINIZIONE FORMALE DELLE CP-NET ........................................................................ 23 4.5.2 ABILITAZIONE E SCATTO DI TRANSIZIONI NELLE CP-NET ................................................. 25 4.5.3 VANTAGGI DELLE CP-NET ....................................................................................... 27 4.6 4.7 RETI PREDICATI/TRANSIZIONI ..................................................................................... 28 RETI TEMPORIZZATE .................................................................................................29

4.7.1 RETI TEMPORIZZATE DETERMINISTICHE ....................................................................... 30 4.7.2 RETI TEMPORIZZATE STOCASTICHE ............................................................................ 33 5. FONTI ................................................................................................................... 35

2

1. IntroduzioneLe Reti di Petri, ideate nel 1962 da Carl Adam Petri, sono uno strumento per la modellizzazione di processi ed in particolare per la modellizzazione delle comunicazioni e delle interazioni fra processi paralleli. Nella descrizione di un processo (produttivo, organizzativo, ecc.) spesso si ha la necessit di rappresentare sottoprocessi o attivit che possono essere eseguite contemporaneamente, in parallelo fra loro, ma non

indipendentemente luna dallaltra: potrebbe accadere che un determinato passaggio o una certa fase del processo non possa verificarsi o non possa essere attivata fintanto che altre fasi o attivit non siano concluse o fino al verificarsi di determinate condizioni. Situazioni di questo tipo non possono essere descritte mediante un diagramma di flusso, come quelli utilizzati correntemente per la descrizione di un algoritmo nellambito della programmazione strutturata. In un diagramma di flusso le attivit sono rigidamente serializzate: due rami distinti di un diagramma di flusso non vengono mai percorsi contemporaneamente, ma rappresentano due strade alternative scelte secondo un criterio rigidamente deterministico dipendente dallesito della valutazione di una espressione booleana. Con le Reti di Petri questo limite (la serializzazione dei passi del procedimento) viene superato, ma viene anche introdotto un formalismo grafico e semantico che permette di aggiungere una dimensione ulteriore rispetto ai diagrammi di flusso. Esse, infatti, non solo permettono di rappresentare e di descrivere globalmente un processo, ma consentono anche di seguirne levoluzione permettendo di visualizzare lo stato in cui si trova in un certo istante la rete. Questo formalismo ha conosciuto una rapida diffusione grazie alla sua potenza espressiva, ed ora esistono moltissime varianti pensate per analizzare determinati aspetti di un sistema reale: lo sviluppo delle reti ha ingenerato una modifica delle regole iniziali che si sono adattate alla tipologia e alla natura diversa delle situazioni sotto esame. Per questo motivo nel corso degli anni le diverse tipologie/estensioni delle reti Petri hanno assunto nomi diversi. 3

Scopo di questa tesina proprio quello di descrivere e analizzare alcune tra le principali classi ed estensioni non prima di avere illustrato le reti di Petri generali e le pi conosciute RdP Posti/Transizioni.

2. Le Reti di PetriLe reti di Petri rappresentano un metodo per risolvere una serie molto vasta e complessa di problemi. Inizialmente utilizzate per la progettazione di sistemi informatici, hanno avuto negli ultimi anni un notevole sviluppo ed un ampliamento del loro campo di applicazione: esse si prestano molto bene per rappresentare comportamenti complessi come la sincronizzazione, il succedersi asincrono di eventi, operazioni concorrenti, conflitti e condivisione di risorse. Si possono, quindi, definire come dei modelli astratti e formali atti a rappresentare la dinamica di sistemi che esibiscono attivit asincrone e concorrenti. Due sono sostanzialmente i motivi che le rendono utili. Da un lato consentono di dare al modello di un sistema il rigore formale necessario sia per eliminare ogni fonte di ambiguit nella rappresentazione, sia per effettuare analisi e verifiche sul comportamento del sistema; dallaltro il formalismo delle Reti di Petri suscettibile di una rappresentazione grafica piuttosto semplice, che ne facilita luso anche con

strumenti dedicati assistiti da calcolatore. In una Rete di Petri (dora in avanti chiamate PN, abbreviazione di Petri Net) gli elementi fondamentali sono due: i posti, che definiscono lo stato del sistema, e le transizioni, che invece modificano lo stato. Lo stato di un sistema dato dallunione di pi stati parziali e indipendenti mentre la transizione in generale non riguarda lo stato globale del sistema, ma si limita a variarne solo una parte. Pertanto due eventi che in uno stato possono da due verificarsi transizioni luno della indipendentemente dallaltro rete che possono avere vengono luogo

rappresentati

concorrentemente.

4

2.1

Definizione formale delle Reti di Petri

Una PN generale pu essere definita da una tripla PN = (P, T, A) dove P detto insieme (finito) dei posti, T detto insieme (finito) delle transizioni ed A detto insieme degli archi o relazione di flusso. Inoltre devono valere le seguenti propriet: 1. P T = 2. P T 3. A (P x T) (T x P) La 1 afferma che linsieme dei posti P e linsieme delle transizioni T sono disgiunti. La 2 impone alla rete di non essere vuota cio deve esserci almeno un posto o una transizione. La 3 afferma che un arco A connette soltanto nodi di tipo diverso, ossia lega posti a transizioni e transizioni a posti, ma non posti a posti o transizioni a transizioni. In generale i posti vengono utilizzati per contenere informazioni relative ai possibili stati parziali della rete, cio relative alle componenti dello stato globale, mentre le transizioni indicano le modifiche elementari dello stato della rete, ovvero indicano un evento e il cambiamento negli stati parziali che inducono. Gli archi, infine,

evidenziano in quali condizioni possono presentarsi certi eventi e come il manifestarsi di tali eventi modifichi lo stato del sistema. La rete, quindi, evidenzia la struttura topologica del sistema, indicando quale sia lordinamento che deve valere fra i nodi, e di conseguenza quali eventi possono avere luogo e in quale ordine.

2.2

Le Reti Posti/Transizioni (P/T)

Una prima estensione delle PN generali sono le reti Posti/Transizioni (o reti P/T). Una rete P/T una quintupla P/T = (P, T, A, W, M0) dove P, T ed A definiscono una rete generale e W e M0 sono due funzioni: 1. W: A + 2. M0: P 5

La (1) associa a ogni elemento (arco) della relazione di flusso un numero intero positivo detto peso o molteplicit, e la (2) definisce la marcatura iniziale della rete M0, che associa ad ogni posto un numero intero non negativo di marche (o gettoni o token). La marcatura di tutti i posti della rete (descritta da un vettore M = [m1, m2, ..., m|P|] tale che mi=k, se il posto pi contiene k gettoni) definisce lo stato globale della rete: a partire da M0, tramite il verificarsi di eventi, la rete P/T evolve, portandosi in nuove marcature M: P . Lassegnazione di una marcatura iniziale definisce, quindi, quali siano le marcature in cui effettivamente la rete pu giungere dopo che si sia verificata una qualsiasi successione ammissibile di eventi.

2.2.1 Rappresentazione graficaUna rete P/T viene rappresentata come un grafo bipartito, i cui nodi sono di due tipi distinti (posti e transizioni) e sono collegati tramite archi orientati. In particolare, tramite cerchi o ellissi si rappresentano i posti, tramite rettangoli o barre si

rappresentano le transizioni e tramite frecce gli elementi della relazione di flusso. Una rete P/T composta quindi da: un insieme di posti P = {p1, p2, , pn}; un insieme di transizioni T = {t1, t2, , tm}; un insieme di archi di ingresso AI P T; un insieme di archi di uscita AO T P; una funzione peso W : AI AO - {0} che d un peso a ogni arco (peso 1 se omesso); una funzione marcatura iniziale M0 : P che stabilisce il numero iniziale di token di ogni posto.

6

Fig. 2.1: Elementi di una PN

Fig. 2.2: Esempio di rete P/T

2.2.2

Evoluzione della rete P/T

Prima di osservare come una PN si evolve introduciamo i concetti di preset e postset. Si definisce preset di un nodo della rete di Petri (posto o transizione) linsieme di nodi immediatamente a monte del nodo stesso, mentre si definisce postset linsieme di nodi immediatamente a valle. Si indica il preset di un nodo x con x o pre(x) e il postset con x o post(x). Poich la relazione di flusso A connette posti a transizioni (o viceversa) e non posti a posti n transizioni a transizioni, il preset ed il postset di un posto sono composti di sole transizioni, mentre il preset ed il postset di una transizione sono fatti di soli posti.

Fig. 2.3: Esempio di preset e postset

Levoluzione di una rete di Petri determinata dal verificarsi di uno o pi eventi che hanno la possibilit di accadere nel sistema. Un evento caratterizzato da due attributi: 7

a) la possibilit che esso accada abilitazione di una transizione b) leffetto del suo accadimento sul sistema scatto di una transizione

Abilitazione di una transizione Perch una transizione possa scattare ( transizione abilitata) devono essere verificate alcune condizioni, che dipendono dal peso degli archi in ingresso alla transizione e dalla marcatura dei posti in ingresso alla stessa. I posti in ingresso a una transizione sono associati a pre-condizioni per il verificarsi dellevento associato alla transizione. Poich la marcatura della rete ne rappresenta lo stato, labilitazione di una transizione dipende dalla marcatura corrente. Una transizione abilitata se tutti i posti del suo preset contengono un numero di token almeno pari al peso dellarco che li connette alla transizione.

Fig. 2.4: Esempi di transizioni abilitate e non

Scatto di una transizione Lo scatto di una transizione abilitata determina il consumo di gettoni nei posti a monte e la generazione di gettoni nei posti a valle. I posti in uscita sono associati a postcondizioni dellevento. Leffetto dello scatto di una transizione determina un

cambiamento della marcatura della rete. Lo scatto di una transizione provoca la rimozione da ogni posto a monte (cio nel suo preset) e laggiunta ad ogni posto a valle (cio nel suo postset) di un numero di

8

gettoni pari al peso degli archi che la collegano a tali posti. La marcatura di tutti i posti che non siano n di ingresso n di uscita alla transizione rimane inalterata.

Fig. 2.5: Esempio di scatto di transizione

Bisogna fare unimportante osservazione sullo scatto di una transizione. Nel corso dellevoluzione della rete, lo scatto delle transizioni provoca un flusso di token. Tuttavia, non bene pensare (come invece si potrebbe essere portati a fare) che i token attraversino la transizione. molto pi corretto pensare che i token tolti dai posti di preset scompaiano e che si creino token nei posti di postset (che infatti possono essere in numero diverso). Nellesempio di fig. 2.5 si nota che scompaiono 4 token dal preset di T1 e se ne creano 5 nel postset: ci dimostra losservazione appena fatta.

2.2.3

Non determinismo

La regola di scatto non sufficiente a determinare compiutamente levoluzione di una rete perch, in una generica marcatura, pu accadere che pi transizioni risultino abilitate allo scatto (e chiaramente se si sceglie di farne scattare certune o certe altre levoluzione futura della rete non la stessa). Nelle reti P/T standard si assume per convenzione che scatti una sola transizione, scelta a caso (non determinismo). Questo criterio garantisce il rispetto della localit dellevoluzione del sistema, cio lindipendenza degli eventi. Una volta che una transizione abilitata scatta, per decidere quale sar la futura transizione abilitata a scattare si deve attuare una nuova valutazione della rete, in quanto la marcatura creatasi dallo scatto della precedente transizione pu aver abilitato nuove transizioni e aver disabilitato alcune di quelle abilitate in precedenza.

9

Una regola alternativa (molto diffusa nei programmi per la simulazione di reti di Petri) stabilisce che transizioni abilitate ma non in conflitto scattino tutte. Quanto a quelle in conflitto, vi sono molte convenzioni diverse: scelta casuale, priorit, ecc. La scelta casuale della transizione che scatta ha senso in un modello concettuale di un problema, ma non va bene in fase di implementazione. Si immagini ad esempio di dover progettare un controllore: occorre fornire regole certe di evoluzione!

2.2.4Sequenza

Strutture modellistiche fondamentali

Due transizioni t1 e t2 si dicono in sequenza, e t1 precede t2 in una data marcatura, se con t1 abilitata, lo scatto di t1 abilita t2.

Fig. 2.6: Sequenza

Conflitto strutturale ed effettivo Due transizioni t1 e t2 si dicono in conflitto strutturale se hanno almeno un posto dingresso in comune. Due transizioni in conflitto strutturale sono in conflitto effettivo in una marcatura M se sono entrambe abilitate ed il numero di token che i loro posti dingresso contengono non sufficiente a soddisfare tutti i pesi degli archi che li collegano alle due transizioni (lo scatto di una disabilita laltra). Il conflitto strutturale dipende dalla topologia della rete, il conflitto effettivo anche dalla marcatura corrente.

Fig. 2.7: Conflitto strutturale ed effettivo

10

Concorrenza strutturale ed effettiva Due transizioni t1 e t2 si dicono in concorrenza strutturale se non condividono nessun posto dingresso (lo scatto di una non disabilita laltra). Due transizioni sono in concorrenza effettiva se condividono uno o pi posti dingresso ma esiste una marcatura M per cui lo scatto di una transizione non disabilita laltra.

Fig. 2.8: Concorrenza strutturale

Fig. 2.9: Concorrenza effettiva

Sincronizzazione e inizio concorrenza Due strutture legate al concetto di concorrenza sono la transizione di sincronizzazione (pi posti a monte abilitano una transizione) e quella di inizio concorrenza (pi posti a valle di una transizione ricevono gettoni contemporaneamente, allo scattare di una transizione). Tipicamente, due sequenze concorrenti sono attivate dallo scatto di una transizione del secondo tipo e la fase di concorrenza termina con lo scatto di una transizione del primo tipo.

Fig. 2.10: Transizione di sincronizzazione e transizione di inizio concorrenza

11

3. Classi particolari di Reti di PetriNel seguito si introdurranno alcune classi di reti di Petri utili ai fini dellanalisi di sistemi. Tipicamente, se rispetto al modello di reti P/T definito nei paragrafi precedenti si applicano restrizioni, si ottiene una rete con minore potere rappresentativo ma con maggiori possibilit di ottenere risultati analitici. Se, al contrario, si aggiungono caratteristiche e attributi alle reti P/T standard, si ottiene un modello in grado di rappresentare una classe pi vasta di sistemi, ma al prezzo di una diminuzione delle possibilit di analisi teoriche. Saranno presentate tre classi particolari di PN: Macchine a stati Grafi marcati Reti a scelta libera

3.1

Macchina a Stati (State Machine SM)

Una macchina a stati (automa) una rete di Petri nella quale ogni transizione limitata ad avere esattamente un solo posto dingresso e un solo posto duscita, tutti gli archi hanno peso unitario e tutte le marcature prevedono un unico token (la sua posizione in un posto o in un altro determina lo stato della rete).

Fig. 3.1: Esempi di macchine a stati

La macchina a stati strettamente conservativa: questo significa che il numero delle marche nella rete non cambia mai, ovvero che il sistema finito. 12

Inoltre, una macchina a stati viva se e solo se fortemente connessa, cio se possibile andare da un qualunque nodo ad un altro, seguendo la relazione di flusso, e se ha almeno un gettone. Una macchina a stati pu rappresentare conflitti (posto con pi transizioni in uscita), ma non pu modellizzare la creazione e la distruzione di gettoni necessaria per rappresentare la concorrenza e la sincronizzazione.

3.2

Grafo marcato (Marked Graph MG)

Un grafo marcato il duale di una macchina a stati, ovvero una rete di Petri nella quale ogni posto limitato ad avere esattamente una sola transizione dingresso ed una sola transizione duscita.

Fig. 3.2: Esempio di grafo marcato

Mentre una macchina a stati pu facilmente rappresentare conflitti mediante un posto con molte transizioni in uscita e non la creazione e la distruzione di marche necessarie per modellare la simultaneit o gli eventi legati allattesa nelle fasi di sincronizzazione, i grafi marcati possono modellare la simultaneit e la sincronizzazione ma non i conflitti o le decisioni dipendenti da dati.

3.3

Rete a Scelta Libera (Free Choice PN FC)

Questa classe di reti di Petri permette di rappresentare sia i conflitti tipici delle macchine a stati sia la simultaneit tipica dei grafi marcati, anche se in maniera limitata.

13

Losservazione che conduce a definire reti a scelta libera che, combinando le situazioni di conflitto e di concorrenza, potrebbero nascere situazioni di non chiara evoluzione (cosiddette situazioni di confusione).

Fig. 3.3: Situazione di confusione

Le reti a scelta libera sono reti che escludono le configurazioni di confusione, garantendo quindi che i conflitti vengano risolti indipendentemente dalla marcatura della rete. Una rete a scelta libera una rete di Petri tale che per ogni arco da un posto ad una transizione o quel posto lunico posto in ingresso alla transizione (non c sincronizzazione), oppure quella transizione lunica transizione in uscita da quel posto (non ci sono conflitti).

Fig. 3.4: Esempi di reti FC

Limportanza delle reti free-choice sta nel modo in cui in esse sono permessi conflitti controllati: essi accadono solamente quando un posto in ingresso a molte transizioni. Nelle reti free-choice, se un posto in ingresso a molte transizioni (conflitto potenziale), allora esso lunico ingresso per tutte queste transizioni. Questo permette di scegliere liberamente (cio indipendentemente dalla marcatura) lattivazione di una transizione, perch la presenza o meno di marche negli altri posti della rete non coinvolge la scelta della transizione da attivare.

14

Si deduce, infine, che una macchina a stati e un grafo marcato sono reti a scelta libera, ma non vale il viceversa.

3.4

Rete a Scelta Libera Estesa (Extended Free Choice PN EFC)

Una rete a scelta libera estesa tale che se due posti hanno una transizione di uscita in comune, allora quei posti hanno le stesse transizioni duscita.

Fig. 3.5: Esempio di rete EFC

Una rete a scelta libera anche una rete a scelta libera estesa, ma non vale il viceversa.

3.5

Rete a Scelta Libera Asimmetrica (Asymmetric Free Choice PN AFC)

Una rete a scelta asimmetrica una rete di Petri tale che se due posti hanno delle transizioni di uscita in comune, linsieme di transizioni di uscita di un posto contiene quello dellaltro.

Fig. 3.6: Esempio di rete AFC

Una rete a scelta libera estesa anche una rete a scelta libera asimmetrica, ma non vale il viceversa.

3.6

Rete Ordinaria

In una rete di Petri ordinaria ammissibile anche una struttura come quella della figura 3.6, che incompatibile con tutte le definizioni precedenti. 15

Fig. 3.7: Esempio di rete ordinaria

Una rete a scelta libera asimmetrica anche una rete ordinaria, ma non vale il viceversa.

3.7

Legami tra le varie tipologie di rete

Fig. 3.8: Reti di Petri ordinarie AFC EFC FC (SM MG)

4. Estensioni di Reti di PetriLe reti di Petri classiche o P/T fin qui presentate costituiscono uno dei primi modelli di rete definiti in letteratura. Esse risultano utili per analisi qualitative di un sistema, ad es. per verificare se una marcatura raggiungibile a partire da unaltra. Tuttavia, nonostante il loro elevato potere espressivo e la loro immediatezza rappresentativa, le reti P/T hanno

16

delle carenze nella rappresentazione di un cospicuo numero di situazioni e nella modellizzazione di grandezze come il tempo. Per ampliare il loro potere di modellazione, le reti P/T sono state variamente estese. Esistono, infatti, molte tipologie/estensioni di reti di Petri: alcune di esse sono completamente retro-compatibili (ad esempio le reti di Petri innestate) 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 temporizzate). Se possono essere modellate nella rete di Petri originale, esse non sono reali estensioni ma sono modi convenienti di far vedere la stessa cosa, e possono essere trasformate con opportune formule matematiche nell'originale rete, senza perdere di significato. 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. Si osserva, infatti, che le estensioni, mentre aumentano il potere espressivo dei modelli di reti di Petri, purtroppo ne compromettono o complicano le possibilit di analisi. Diventa difficile provare (ossia dimostrare) propriet di un modello esteso e spesso ci che rimane al modellatore lesecuzione diretta della rete. Le estensioni, infine, avvicinano le reti a dei veri linguaggi di programmazione ad alto livello; un modello corrisponde cos ad un programma. In questa sezione si illustreranno alcune tra le principali estensioni di reti di Petri e se ne descriveranno funzionamento e propriet.

4.1

Reti a Capacit Limitata

Le reti a capacit limitata sono reti in cui i posti hanno associata una capacit che definisce il numero massimo di marche ammesso: se lo scatto di una transizione comportasse il superamento di capacit di un suo posto duscita, la transizione risulterebbe non abilitata.

17

Questa estensione pu essere utilizzata per rappresentare magazzini o pool di risorse a capacit limitata.

Fig. 4.1: Esempio di PN con capacit limitata con transizione non abilitata

Nellesempio di fig. 4.1 si pu notare che, sebbene il suo preset lo permetta, la transizione non pu essere abilitata perch il suo posto duscita D di capacit 5 non pu superare tale numero, quindi non pu contenere 6 marche (3 marche iniziali + altre 3 date dal peso dellarco di uscita). Una PN a capacit limitata data da una sestupla PN = (P, T, A, W, M0, K), dove P, T, A, W, M0 sono gli stessi elementi di una rete di Petri P/T mentre K: P + un insieme di

restrizioni sulla capacit, che assegna ad ogni posto p P un numero positivo n + cheindica il numero massimo di token che possono occupare quel posto. Una rete in cui ogni posto ha una capacit k nota come una rete di Petri k-bounded o k-limitata.

Fig. 4.2: Evoluzione di una PN a capacit limitata

Nella figura 4.2, la fig. a rappresenta una PN il cui posto P2 ha una capacit pari a 2. La transizione T1 abilitata e il suo scatto risulta in fig. b; in questa figura sono abilitate le transizioni T1 e T2. Il nuovo scatto di T1 risulta nella fig. (c): in questa figura la transizione 18

T1 non pu pi scattare, sebbene ci sia ancora un token in P1, perch la marcatura di P2 ha raggiunto la sua capacit massima.

4.2

Reti con Archi inibitori

Un particolare tipo di rete di Petri estesa quella in cui sono presenti degli archi speciali denominati archi inibitori (o negatori). Si tratta di archi, eventualmente pesati, in ingresso ad una transizione, che incidono sulla sola condizione di abilitazione. Essi hanno una funzione disabilitante (inibente): la transizione a cui sono collegati abilitata se la marcatura del posto minore del peso dellarco inibitore. Questi archi, inoltre, sono detti impropri, poich non danno luogo a spostamenti di token nella rete. In generale, se il peso di un arco inibitore Pi Tj s, allora la transizione Tj abilitata se e solo se la marcatura m(Pi) < s (threshold test). Il caso s = 1 un caso particolare detto

zero test in quanto la transizione Tj abilitata se e solo se m(Pi) < 1, cio se m(Pi) = 0.Graficamente, al posto della punta della freccia larco inibitore reca un piccolo cerchio, che rappresenta una negazione.

Fig. 4.3: Esempio di PN con arco inibitore

La transizione in fig. 4.3 abilitata poich m(A) < 2, m(B) >=1 e m(C) >=3. Lo scatto sottrae un token da B, 3 da C, e ne aggiunge 3 in D.

19

Fig. 4.4: Transizioni con archi inibitori

In fig. 4.4, invece, sono presenti una transizione non abilitata a causa della mancanza di gettoni in P1 (a), unaltra transizione non abilitata per la presenza di un gettone in P2 (b) ed una PN con arco inibitore, prima (c) e dopo levoluzione (d).

4.3

Reti con Priorit

Un'ulteriore estensione delle Reti di Petri costituita dalle Reti di Petri con priorit usate per risolvere situazioni di conflitto effettivo. In tali reti, la scelta di quale fra le transizioni abilitate debba scattare deterministica e precisamente basata sulla priorit di tali transizioni. In generale, una transizione non pu scattare se una transizione di priorit pi alta abilitata. Date due transizioni t1 e t2, t1 t2 (o t1 < t2) indica che labilitazione di t1 induce

linibizione di t2 (t1 pi prioritaria di t2). Vale anche la transitivit: date tre transizioni t1, t2 e t3, se t1 t2 e t2 t3, allora vale t1 t3 (t1 pi prioritaria di t3).

Fig. 4.5: PN con priorit con marcatura m1= (1, 1, 0)

Nella PN in figura sopra, si possono osservare due conflitti strutturali, e , ma due differenti conflitti effettivi, e (T4 non attivabile perch P3 non marcato). Per risolvere tali conflitti vengono assegnate le 20

priorit poste a destra della rete. Con la marcatura m1= (1, 1, 0) (che indica P1 e P2 marcati e P3 no), poich T2 < T1 e T2 < T3, la transizione che scatta T2 (ha priorit pi alta). Se la marcatura fosse del tipo m2= (0, 1, 1) o m3 = (1, 1, 1), allora la transizione che scatterebbe sarebbe T4 (ha priorit massima).

Fig. 4.6: Grafo di priorit

4.4

Reti innestate

Al crescere della loro complessit, le reti di Petri diventano sempre meno leggibili. Per aumentarne la leggibilit e per rappresentare sistemi complessi, possibile utilizzare transizioni innestate che consentono una descrizione top-down della rete complessiva. Tali transizioni consentono di innestare altre PN: mediante opportuni raffinamenti possibile descrivere modelli complessi di PN tramite PN pi semplici e strutture gerarchiche. Un raffinamento (sottorete) una PN che d una descrizione pi dettagliata di un nodo. Una transizione innestata (denotata graficamente con un doppio rettangolo o una doppia barra) un elemento di T (insieme delle transizioni) a cui viene associato il nome di una sottorete. Il suo comportamento il seguente: quando il preset di tale transizione marcato, la marcatura si sposta nellinsieme di start place della sottorete e questa viene eseguita; quando lesecuzione della sottorete arriva al termine, il postset della transizione innestata nella rete principale viene marcato e lesecuzione di questultima riprende.

21

Una rete di Petri innestata o gerarchica completamente retro-compatibile, cio pu essere trasformata in una rete P/T standard con conseguente aumento della complessit e diminuzione della leggibilit della stessa.

4.5

Reti Colorate

Le Reti di Petri Colorate (CP-Net o CPN) rappresentano un linguaggio di modellazione sviluppato per i sistemi in cui la comunicazione, la sincronizzazione e la condivisione delle risorse svolgono un ruolo importante. Le CP-net combinano i punti di forza delle ordinarie Reti di Petri con i punti di forza di un linguaggio di programmazione ad alto livello. In questa estensione di PN, ad ogni posto associato un tipo che determina il tipo di dati che il posto pu contenere. I valori che possono assumere i tipi associati ai posti vengono dichiarati al di fuori della rete, vicino ai posti; le dichiarazioni quindi, implicitamente, specificano le operazioni che possono essere eseguite sui valori dei tipi di dati. Il token, quindi, un valore che appartiene al tipo associato al place. Ad ogni valore assunto da un token associato un colore; di conseguenza ad ogni tipo di dato associato un insieme di colori (colour set). Questa associazione permette di considerare i token di una CP-net in modo distinto luno dallaltro in contrapposizione con le ordinarie Reti di Petri P/T che hanno token indistinguibili. Inoltre, in ogni posto ammesso che ci siano due o pi gettoni dello stesso colore; questo fa s che si abbiano multi-set di token. Una marcatura di una CP-net una funzione che associa ad ogni place un multi-set di token del tipo corretto. La marcatura iniziale M0 specificata con una espressione di inizializzazione. Omettere tale espressione implica che la marcatura iniziale corrisponde al place vuoto, cio non contiene token. Uno stato di una CP-net identificato

dallinsieme delle marcature, ossia dal numero di token su ogni singolo place.

22

Le azioni di una CP-net, come nelle P/T net, sono rappresentate da transizioni. Un arco di arrivo indica che la transizione pu rimuovere token dal corrispondente posto, mentre un arco in uscita indica che la transizione pu aggiungere token. Il numero esatto di token e il loro rispettivo valore sono determinati mediante una arc

expression (posizionata vicino allarco). La valutazione dellespressione permette loscatto di una transizione. Una espressione pu contenere variabili libere, funzioni o costanti a cui associato un tipo. In presenza di una variabile libera, si deve vincolare la variabile ad un valore preciso che appartiene al suo tipo, in caso contrario, non si in grado di valutare le espressioni. La coppia transizione vincolo detta binding. Quindi, se il binding si verifica esso rimuove token dai posti di input e aggiunge token ai posti di output; da ci ne consegue che lattivazione del binding possibile se i token che devono essere rimossi esistono. Luso di variabili in arc expression significa che ogni transizione di una CP-net pu verificarsi in molti modi diversi tra loro, in modo simile a come pu essere eseguita una procedura con diversi parametri di input. Pertanto si pu utilizzare una singola transizione per descrivere una classe di attivit connesse tra di loro, mentre in una P/T net abbiamo bisogno di una transizione per ogni istanza di tale attivit. In aggiunta alle arc expression, possibile associare unespressione booleana per ogni transizione, chiamata guardia. Essa precisa che si accettano solo gli elementi vincolanti per la quale lespressione booleana valutata true.

4.5.1 Definizione formale delle CP-netIntrodotti tutti gli elementi di una CP-net ne diamo ora la definizione formale. Una rete di Petri colorata definita come una tupla CPN = {, P, T, A, N, C, G, E, I} dove: un insieme non vuoto di tipi, chiamato insieme di colori (colour set).

23

Linsieme di tipi determina i valori che possono assumere i dati, le operazioni e le funzioni che possono essere utilizzate nelle espressioni (ad esempio, expression, nella funzione guardia, nelle espressioni di inizializzazione). P un insieme finito di posti (places) T un insieme finito di transizioni (transitions) A un insieme finito di archi, tale che: P T = P A = T A = I posti, le transizioni e gli archi sono descritti da tre insiemi P, T e A finiti e a coppie disgiunte. Imponendo che questi insiemi siano finiti si evita una serie di problemi tecnici come la possibilit di avere un numero infinito di archi tra due nodi. N la funzione Nodo. Essa definita da A (P x T) (T x P) I due nodi devono essere di tipo diverso (ad esempio, uno deve essere un place mentre laltro una transition). G la funzione Guardia. Essa definita da T EXPR, tale che: nelle arc

t T: [Type(G(t)) = B Type(Var(G(t))) ] dove B denota il tipo booleano.Questa funzione associa ad ogni transizione t, una espressione booleana dove tutte le variabili hanno tipi che appartengono a . Quando si omettono le espressioni di guardia queste vengono valutate sempre vere. C la funzione Colore. Essa definita da P . Questa funzione associa ad ogni place p un tipo C(p). Intuitivamente questo significa che ogni token su p deve avere un valore che appartiene a C(p). E la funzione Arco Espressione. Essa definita da A EXPR, tale che:

aA, p(a)N(a) : [Type(E(a)) = C(p(a))MS Type(Var(E(a))) Questa funzione associa ad ogni arco, a, una espressione di tipo C(p)MS. Ci vuol dire che ogni arco espressione deve valutare i multi-set di token sulla base del tipo del place adiacente, p, ed i tipi delle variabili che appartengono al colour set. I un funzione di inizializzazione. Essa definita da P EXPRCLOSED, tale che:

p P: [Type(I(p)) = C(p)MS]24

Questa funzione associa ad ogni place p unespressione chiusa che deve essere di tipo C(p)MS. Quando rappresentiamo una CP-net e omettiamo lespressione di

inizializzazione questa viene valutata .

4.5.2 Abilitazione e scatto di transizioni nelle CP-netLesempio di CP-net proposto in fig. 4.7, servir per capire come avviene labilitazione e lo scatto di transizioni in un rete di Petri colorata. Esso descrive un semplice protocollo che trasporta pacchetti di dati da un sender ad un receiver. Nella rete sono presenti 7 posti (rappresentati con cerchi o ellissi), 5 transizioni (rappresentati con rettangoli), un insieme di archi orientati che collegano posti a transizioni o transizioni a posti ed, infine, delle iscrizioni vicino ai posti, alle transizioni e agli archi (mediante il linguaggio di programmazione CPN ML). Per convenzione, si scrivono i nomi dei posti (delle transizioni) allinterno dei cerchi (dei rettangoli).

Fig. 4.7: Protocollo di comunicazione modellizzato con CP-net

25

Come detto in precedenza, ogni posto pu essere marcato con uno o pi token, ed ogni token ha un proprio valore (colore del token). Sono il numero ed i colori dei token di ogni posto che insieme rappresentano lo stato del sistema (marcatura della CPN). Per convenzione, si scrive il numero dei token in un piccolo cerchio accanto ad ogni posto. Sotto ad ogni posto, invece, sono presenti delle iscrizioni in maiuscolo che indicano il tipo dellinsieme dei colori possibili. I posti NextSend, C e D hanno il colour set NO (che in ML sta per integer); i rimanenti posti hanno il colour set NOxDATA che definito come il prodotto tra il tipo NO ed il tipo DATA ossia contiene tutte le coppie dove il primo elemento un intero ed il secondo una stringa. Liscrizione in alto a destra dei posti indica, invece, il marking iniziale dei place (allinterno di box). Per NextSend liscrizione ML 1 1 evidenzia che quel posto contiene un token di valore (colore) 1; per

PacketsToSend liscrizione denota la presenza di coppie di token (1,"COL"), (2,"OUR"), (3,"ED "), (4,"PET"), (5,"RI "), (6,"NET"). I simboli ++ e sono operatori usati per costruire il multi-set che consiste, in questo caso, di 6 colori. Lassenza di iscrizioni di questo tipo per gli altri posti indica lassenza di token per quei posti. Quando una transizione scatta, essa rimuove token dai suoi posti di input e li aggiunge nei suoi posti di output. I colori dei token che sono rimossi dai posti di input e aggiunti nei posti di output sono determinati per mezzo delle arc expression, iscrizioni testuali poste vicino agli archi, costituite da variabili, costanti, funzioni e operatori. Solo quando tutte le variabili di unespressione sono vincolate ai valori del tipo corretto, allora lespressione pu essere valutata. Sono proprio le arc expression degli archi in input di una transizione che determinano labilitazione della stessa. Per abilitare una transizione, quindi, deve essere possibile trovare un binding per le variabili che compaiono sulle arc expression in input ad essa.

26

Fig. 4.8: Parte della CP-net di fig. 4.7

Nella CPN di fig. 4.8, le due variabili n e d, devono vincolare rispettivamente ad un valore di tipo NO (intero) e DATA (stringa). Quando la transizione SendPacket (lunica abilitata) scatta, essa rimuove un token sia da PacketToSend sia da NextSend. La variabile n posta sullarco che collega NextSend a SendPacket viene vincolata ad 1 (il colore del relativo token). Fatto questo si cerca un binding della variabile d cosicch larc expression (n, d), posta sullarco che collega PacketToSend a SendPacket, possa valutare uno dei 6 colori di PacketToSend. Lunica possibilit vincolare d alla stringa COL, perci il binding (n=1, d=COL) lunico binding possibile per il marking iniziale della rete. Quindi viene rimosso il token con colore 1 dal posto di input NextSend, viene rimosso il token con colore (1, COL) dal posto di input PacketToSend e viene aggiunto un nuovo token con colore (1, COL) al posto di output A.

4.5.3 Vantaggi delle Cp-netLe CP-net sono utilizzate per tre ragioni diverse ma strettamente connesse tra di loro. Innanzitutto, un modello CP-net una descrizione formale del sistema, e pu essere utilizzato come una specifica (di un sistema da costruire) o come una presentazione (di un sistema per essere spiegato ad altre persone o al modellizzatore stesso). Con la

creazione di un modello si pu studiare, infatti, un nuovo sistema prima di costruirlo. Si 27

tratta di un evidente vantaggio, in particolare per i sistemi in cui gli errori di progettazione possono compromettere la sicurezza o avere costi molto elevati in fase correzione degli stessi. In secondo luogo, il comportamento di una CP-net pu essere analizzato sia attraverso simulazione (automatica o interattiva) sia per mezzo di metodi di analisi pi formale. Con una simulazione automatica, simile ad un programma in esecuzione, lutente si limita ad analizzare i risultati. Con una simulazione interattiva, invece, l'utente ha il pieno controllo: pu vedere gli effetti dei singoli passi direttamente sulla rappresentazione grafica della CP-net. Ci significa che egli pu analizzare i diversi stati e scegliere le transizioni da abilitare. Una simulazione interattiva simile al singolo passo del debug: esso fornisce un modo per "visitare" una CP-net, in modo tale da analizzare i diversi scenari e verificare se il modello funziona come previsto, passo dopo passo.

4.6

Reti Predicati/Transizioni

Un'altra estensione delle reti di Petri sono le reti Predicati/Transizioni (o reti Pr/T), proposte da Genrich e Lautenbach nel 1981 con lo scopo di fornire una nuova dimensione di astrazioni al modello P/T. Il paradigma a cui si fa riferimento di tipo logico e si basa sul calcolo dei predicati del primo ordine. Il vantaggio che se ne ottiene una rappresentazione pi naturale ed immediata dei vincoli che governano l'evoluzione della rete ed una maggiore leggibilit degli oggetti che costituiscono la marcatura della rete stessa. I vantaggi sono per controbilanciati da una maggiore difficolt nell'analisi formale delle propriet strutturali della rete. La marcatura di un posto in una rete Pr/T costituita da un multinsieme di ennuple la cui arit costante e dipende dal posto in esame. Ad esempio, un posto A pu essere interpretato come una relazione fra un abbonato telefonico e il numero di scatti associato; questa coppia costituisce in termini di logica un predicato in quanto relazione 28

fra i due oggetti, da cui il nome del modello. Quindi ciascun posto ha una sua specifica arit, legata all'arit delle relazioni che identifica. Analogamente, sugli archi si avranno etichette che saranno ennuple di variabili di arit uguale a quella del predicato da cui l'arco entra o esce; una sostituzione di tali variabili con delle costanti perci il punto di partenza per verificare se una transizione abilitata o meno. Quindi ogni transizione avr un predicato detto guardiano ad essa associato che dovr essere verificato in base alla sostituzione delle variabili con le costanti che arrivano dai posti ad essa connessi. In conclusione, una transizione abilitata se esiste una sostituzione di variabili delle etichette degli archi entranti nella transizione che soddisfi la duplice richiesta di generare ennuple presenti nei posti di ingresso alla transizione e di rendere vero il guardiano associato alla transizione stessa.

4.7

Reti Temporizzate

Nei paragrafi precedenti stato evidenziato come le reti di Petri siano uno strumento potente per lo studio di caratteristiche strutturali e qualitative dei sistemi a eventi discreti (SED). altrettanto evidente che, qualora si desideri analizzare le prestazioni di un SED, cio effettuarne uno studio quantitativo, le reti posto/transizione non sono uno strumento adatto, perch prescindono dalla durata delle singole attivit che avvengono nel sistema. Si dunque deciso che, per rendere le reti di Petri uno strumento utile per la

valutazione delle prestazioni, deve essere introdotta in esse una qualche metricatemporale: da qui nascono le reti di Petri temporizzate (TPN). Come strumento modellistico, esse offrono molti vantaggi che possono essere sintetizzati nei punti che seguono: Forniscono un ambiente idoneo ad una corretta e dettagliata rappresentazione di un sistema; esse infatti, come le reti posto/transizione, sono regolate da semantiche ben

29

definite che, oltre che costituire la base per i metodi di analisi formale, consentono di realizzare simulatori TPN. Possono riprodurre esattamente caratteristiche proprie dei SED quali priorit, sincronizzazione, uso di risorse condivise. Possono essere utilizzate nello stesso tempo come modelli logici e prestazionali. Lanalisi di TPN pu essere effettuata in modo automatico mediante luso di strumenti informatici dedicati. Ovviamente l'introduzione delle caratteristiche temporali aumenta l'espressivit delle reti di Petri, ma presuppone anche la perdita di alcune caratteristiche importanti delle PN ordinarie come la possibilit di decidere localmente se far scattare una transizione (viene tutto regolato dal tempo). Esistono due tipologie di reti di Petri temporizzate:

Reti temporizzate deterministiche: in cui i valori o gli intervalli temporali sono datiin modo deterministico. il caso delle TIME PETRI NETS (Merlin e Farber, 1976) e delle TIMED PETRI NETS (Ramchandani, 1980)

Reti temporizzate stocastiche: in cui i valori o gli intervalli temporali sono dati inmodo probabilistico. il caso delle STOCHASTIC PETRI NETS (Molloy, 1982) e delle GENERALIZED STOCHASTIC PETRI NETS (Ajmone Marsan, Balbo, Conte, 1984).

4.7.1 Reti temporizzate deterministichePer tener conto del tempo sono state introdotte le seguenti estensioni temporali che si possono classificare in due categorie a seconda dell'interpretazione data alle transizioni.

30

TIME PETRI NETS (Merlin e Farber, 1976) Le Time PN sono state definite con lo scopo di modellare il comportamento dei protocolli di comunicazione. Esse sono adatte per analizzare landamento nel tempo di sistemi esistenti. In una Time PN, ogni transizione rappresenta un evento, il cui verificarsi perci istantaneo. Ad ognuna di essa si associa un intervallo [tmin,tmax]: tmin (che deve essere > 0) rappresenta il tempo minimo che deve trascorrere dall'istante in cui la transizione stata abilitata (ossia dall'istante in cui l'ultimo dei token della tupla abilitante giunto nei suoi posti di ingresso); tmax (che deve essere < ) rappresenta il massimo ritardo, rispetto all'istante di abilitazione, entro il quale la transizione deve scattare (a meno che non sia stata disabilitata nel frattempo dallo scatto di un'altra transizione con cui era in conflitto). La transizione forzata a scattare se il ritardo tmax stato raggiunto senza che sia stata disabilitata. Le reti classiche P/T corrispondono al caso tmin= 0, tmax = .

Fig. 4.9: Esempio di Time PN

Lesempio di fig. 4.9 mostra una Time PN avente una transizione t con intervallo [4, 7]. Supponendo che un token arrivi nel posto P3 al tempo 1, nel posto P1 al tempo 3 e nel posto P2 al tempo 5 (abilitando la transizione), t pu scattare in un tempo compreso tra 9 e 12. Essendo, infatti, la transizione abilitata al tempo 5 (istante in cui lultimo token 31

giunto nel suo posto dingresso P2) deve trascorrere un tempo minimo pari a 4 ed uno massimo pari a 7 affinch t possa scattare (5+4 = 9, 5+7 = 12). TIMED PETRI NETS (Ramchandani, 1980) Le Timed PN sono un modello utile per effettuare valutazioni di prestazioni di sistemi ciclici (ad es. protocolli di comunicazione) con la possibilit, per esempio, di calcolare il tempo minimo di ciclo. In una Timed PN, ogni transizione rappresenta un'attivit del sistema, che perci richiede una durata (non nulla) per essere portata a compimento. Ad ogni transizione tj della rete viene associata una durata dj, ossia un ritardo che corrisponde al tempo che deve trascorrere fra la sua abilitazione ed il conseguente scatto. I gettoni rimangono nei posti in ingresso a ciascuna transizione no allo scatto, a meno che un'altra transizione le prelevi a sua volta. Solo se, al termine del ritardo d j, la condizione di abilitazione continua a sussistere (senza che durante questo intervallo venga mai persa), la transizione tj scatta effettivamente facendo s che i gettoni siano prelevati dai posti in ingresso e depositati nei posti in uscita.

Fig. 4.10: Evoluzione temporale della transizione t1 abilitata al tempo 1.

Sia il tempo totale trascorso a partire dallistante 0. Si consideri la figura 4.10: la transizione t1, avente un ritardo d1, abilitata al tempo = 1, e pu scattare al tempo = 1+ d1: si sta, cio, associando alla transizione temporizzata abilitata al tempo = 1 un clock di durata dj che entra in funzione a partire dal tempo 1. Se, durante il lasso di tempo 1 1 + d1, la transizione t1 venisse disabilitata, automaticamente perderebbe

32

il clock associatogli allistante = 1 e quindi non potrebbe pi scattare al tempo previsto = 1 + d1.

4.7.2 Reti temporizzate stocasticheLe reti di Petri temporizzate stocastiche sono reti in cui possibile associare agli intervalli temporali o alle durate introdotti sulle transizioni, delle distribuzioni di probabilit. In tal modo possibile modellare ed analizzare sistemi di tipo stocastico, in cui l'interesse concentrato pi sulle prestazioni medie del sistema, che sul fatto che l'evoluzione del sistema soddisfi prestabiliti vincoli temporali. STOCHASTIC PETRI NET (Molloy, 1982) In una rete di Petri temporizzata stocastica (o SPN) i tempi di scatto delle transizioni sono rappresentati da variabili aleatorie: a ogni transizione temporizzata associato un ritardo descritto da una variabile aleatoria che ha una certa distribuzione. possibile, quindi, associare ad ogni transizione tj il parametro j caratteristico della sua distribuzione. Tutte le transizioni temporizzate abilitate selezionano

casualmente

un

ritardo

dalla

distribuzione di probabilit associata. Una rete di Petri temporizzata stocastica pu essere definita come una struttura algebrica SPN= (PN, Tempo) dove: PN una rete posto/transizione; Tempo: T R+ una funzione associata al set di transizioni T, secondo la quale Tempo (tj) = 1/ j = j = tasso di scatto associato a tj; si definisce = [1, 2, ...] come il vettore delle frequenze di scatto delle transizioni. Per una SPN le regole di scatto sono le stesse di una TPN, con lunica differenza che, in questo caso, la scelta della prossima transizione da far scattare viene effettuata sulla base delle probabilit di scatto delle singole transizioni. 33

Fig. 4.11: Esempio di rete di Petri temporizzata stocastica

GENERALIZED STOCHASTIC PETRI NETS (Ajmone Marsan, Balbo, Conte, 1984) Nelle reti di Petri stocastiche generalizzate (GSPN), in aggiunta alle transizioni temporizzate vi sono le transizioni immediate. Le transizioni temporizzate funzionano come nelle reti stocastiche semplici mentre quelle immediate scattano immediatamente appena abilitate. Le transizioni immediate modellano quelle attivit con tempi di esecuzione trascurabili rispetto agli altri. Nel caso in cui siano abilitate transizioni di entrambi i tipi, scattano solo quelle immediate. Il vantaggio che le marcature con transizioni immediate "durano poco" e vengono trascurate favorendo unanalisi semplificata della rete.

Fig. 4.12: Esempio di rete di Petri stocastica generalizzata

34

5. FontiDAVID, R., ALLA, H., 2005, Discrete, Continuous and Hybrid Petri Nets, New York: Springer-Verlag Berlin Heidelberg. JENSEN, K., 1995, Coloured Petri Nets, Cap. 2, Aarhus: Springer. DENTI, E., Reti di Petri, Universit degli Studi di Bologna: Dipartimento di Elettronica, Informatica e Sistemistica, Disponibile su . ROSSI, M. G., Timed Petri Nets, Politecnico di Milano: Dipartimento di Elettronica e Informazione, Disponibile su . LEVA, A., Analisi matriciale delle reti di Petri (P/T), Politecnico di Milano: Dipartimento di Elettronica e Informazione, Disponibile su . PIRODDI, L., Reti di Petri: definizioni, evoluzione e propriet, Politecnico di Milano: Dipartimento di Elettronica e Informazione, Disponibile su . BOSCHETTO, A., Modellazione dei processi produttivi, Universit di Roma La Sapienza: Dipartimento di Meccanica e Aeronautica, Disponibile su . CLEMENTE, G., Reti di Petri estese, Universit degli Studi di Padova: Dipartimento di Ingegneria dellInformazione, Disponibile su . PERRICCI, G., Modelli formali per Mobile Ad-hoc NETworks MANET, Prova finale in Informatica Specialistica, Universit degli Studi di Bari. RABELLINO, S., Definizione e sperimentazione di una metodologia per la progettazione di

test suite di accettazione per sistemi informativi gestionali , Prova finale in ScienzedellInformazione, Universit degli Studi di Torino. SESSEGO, F., HYPENS: un simulatore per le reti di Petri discrete, continue e ibride, Prova finale in Ing. Elettrica ed Elettronica, Universit degli Studi di Cagliari. 35