Tecniche di programmazione lineare per l'identificazione di reti di Petri

2 CAPITOLO 1. INTRODUZIONE
me di tutte le sequenze di transizioni abilitate di lunghezza minore o uguale a k
sia Lk(N,M0) = L. Da notare che l’insieme L elenca esplicitamente gli esem-
pi positivi, cioè le stringhe che appartengono al linguaggio, ma implicitamente
definisce anche i controesempi, cioè tutte quelle stringhe di lunghezza minore o
uguale a k che non appartengono al linguaggio. Perciò dal linguaggio osservato
si può costruire un insieme di vincoli di abilitazione E , cioè un insieme di coppie
(σ, t) tali che la transizione t è abilitata dopo che la sequenza σ è scattata, e un
insieme di vincoli di disabilitazione D, cioè un insieme di coppie (σ, t) tali che la
transizione t non è abilitata dopo che la sequenza σ è scattata.
Nel precedente lavoro [3] è stato dimostrato che questo problema (ed una corre-
lata serie di problemi di identificazione più generali) può essere risolto usando
la programmazione intera. Lo svantaggio principale di questo approccio è la sua
complessità computazionale, nel senso che il numero di incognite o variabili cre-
sce esponenzialmente con la lunghezza della stringa più lunga in L, rendendo
molti problemi facilmente intrattabili.
In [13] è stato mostrato come trattare lo stesso problema utilizzando tecniche
di programmazione lineare, che riducono significativamente la complessità del-
la risoluzione del problema di identificazione. L’idea principale è quella di cer-
care soluzioni particolari del problema di identificazione che sono chiamate D-
canoniche, cioè reti con un numero di posti uguale alla cardinalità dell’insieme D,
indicata con |D|. È stato dimostrato che: (a) se un dato problema di identificazione
ha soluzione, allora ha anche una soluzione D-canonica; (b) questa particolare so-
luzione può essere calcolata risolvendo un problema di programmazione lineare,
cioè considerando una funzione obiettivo che consente di trovare una rete ottima
secondo un dato indice di prestazione.
Quindi, la procedura proposta identifica una rete il cui numero di posti è pari alla
cardinalità dell’insieme dei vincoli di disabilitazione che può essere grande, seb-
bene possa esistere una rete equivalente, cioè che genera lo stesso linguaggio, con
un numero di posti molto più piccolo. Successivamente viene fornito un criterio
per controllare se la soluzione calcolata ha un numero minimo di posti e, se non è
questo il caso, allora si discutono due approcci per ridurre questo numero.
L’oggetto di questa tesi è lo sviluppo di un pacchetto Matlab che implementi la
procedura descritta in [13] e la validazione sperimentale di tale approccio.
La procedura proposta è stata implementata mediante la versione 6.5 di Matlab.
I problemi di programmazione sono stati risolti per mezzo del software GLPK
versione 4.9, utilizzato in ambiente Matlab.
1.2. RASSEGNA DELLA LETTERATURA 3
1.2 Rassegna della letteratura
L’idea di studiare la struttura di un automa a partire da esempi positivi e contro-
esempi è stata esplorata fin dai primi anni 80 nell’ambito dei linguaggi formali
[15, 16].
Uno dei primi approcci originali all’identificazione di reti di Petri sane è stato
discusso da Hiraishi [7], che ha presentato un algoritmo per la costruzione di un
modello di rete di Petri non etichettata a partire dalla conoscenza di un insieme
finito delle sue sequenze di scatto.
Un differente approccio è basato sulla teoria delle regioni il cui obiettivo è quello
di decidere se un dato grafo è isomorfo al grafo di raggiungibilità di una rete non
etichettata e poi costruirlo. Un ottimo esame di quest’approccio, che presenta an-
che alcuni efficienti algoritmi per la sintesi di una rete basata sull’algebra lineare,
può essere trovato nel lavoro di Badouel e Darondeau [1].
Meda e Mellado [9, 10] hanno presentato un approccio per l’identificazione di reti
di Petri decodificate non etichettate. Il loro approccio consiste nell’osservare la
marcatura di un sottoinsieme di posti e, date alcune informazioni aggiuntive sulla
dipendenza tra le transizioni, permettere di ricostruire la parte della struttura di
rete relativa ai posti non osservati.
Bourdeaud’huy e Yim [2] hanno presentato un approccio per ricostruire la ma-
trice di incidenza e la marcatura iniziale di una rete non etichettata date alcune
informazioni strutturali sulla rete, come l’esistenza di P-invarianti o T-invarianti.
Quest’approccio può anche trattare esempi positivi di sequenze di scatto ma non
controesempi.
Dotoli et al. in [5] hanno considerato un approccio basato sull’ottimizzazione
che fonde alcune caratteristiche di [3], [9] e [10]. La loro procedura assume che
sia data una produzione della rete, cioè non richiede solo la conoscenza delle
sequenze di eventi ma anche delle marcature raggiunte durante questa evoluzione.
Sono date condizioni necessarie e sufficienti per la corretta identificazione della
rete.
Infine, Sreenivas in [17] ha trattato la minimizzazione di modelli di reti di Petri.
Dato un generatore di rete di Petri non etichettata e una funzione peso che associa
al generatore un intero non negativo, l’obiettivo è quello di trovare una rete di Petri
che genera lo stesso linguaggio della rete originale minimizzando il peso dato.
4 CAPITOLO 1. INTRODUZIONE
1.3 Struttura della tesi
Nel seguito verrà illustrata la struttura della tesi.
Nel capitolo 2 vengono fatti dei richiami alle reti P/T introducendo il formalismo
utilizzato nella tesi. Viene definita la struttura algebrica e grafica delle reti P/T, in
particolare le matrici Post e Pre, e vengono richiamate le leggi che ne governano
l’evoluzione dinamica. Poi viene definito il concetto di rete marcata o sistema di
rete, cioè una rete individuata dalle matrici Post e Pre con una marcatura ini-
ziale M0. Viene introdotto il concetto di linguaggio, sia globale, cioè l’insieme
L(N,M0) di tutte le sequenze di scatto abilitate dalla marcatura iniziale, sia par-
ziale, cioè l’insieme Lk(N,M0) delle sequenze di scatto di lunghezza minore o
uguale a k. Vengono poi definite alcune proprietà strutturali di una rete P/T, cioè
indipendenti dalla marcatura iniziale, e infine vengono richiamate alcune classi
particolari di reti P/T.
Nel capitolo 3 vengono fatti dei richiami alla programmazione lineare. Si co-
mincia con l’introduzione della formulazione di tale modello di ottimizzazione
vincolata, in base al quale un programma lineare è un problema di ottimizzazione
con una funzione obiettivo lineare e dei vincoli lineari rispetto a variabili non ne-
gative. Viene mostrata la procedura di soluzione grafica per i programmi lineari
che coinvolgono due o tre variabili, basata sul concetto di poliedro. Poi viene in-
trodotto il metodo del simplesso, il più utilizzato per la risoluzione di questo tipo
di problemi. Successivamente viene presentata la teoria della programmazione
duale in base alla quale un problema di programmazione primario viene risolto ri-
solvendo un associato problema duale. Infine viene descritto il metodo del punto
interno e vengono dati dei cenni alla programmazione intera.
Nel capitolo 4 viene illustrata la procedura di identificazione di una rete P/T pro-
posta da Cabasino et al. in [13]. Il capitolo si apre con una serie di nozioni
preliminari: si definisce una classe di vincoli lineari, che chiamiamo Constraint
Set (CS), e si caratterizzano i CS ideali. Poi viene presentata la procedura di iden-
tificazione di base. Si parte dalla definizione del problema in questione in base
alla quale, dato un linguaggio L finito e chiuso per prefisso costituito da parole di
lunghezza minore o uguale a k e scelto un determinato numero di posti, si vuole
identificare una rete M0, Post e Pre che genera il linguaggio L. Vengono definiti
gli insiemi delle condizioni di abilitazione E e di disabilitazione D e si definisce il
sistema di rete D-canonico, cioè una rete in cui un differente posto è associato ad
ogni elemento di D. Viene definito il CS e viene dimostrato come una sua qualsia-
si soluzione intera sia una soluzione D-canonica del problema di identificazione.
Poi viene mostrato come il numero di vincoli associati ad E e D può essere ri-
1.3. STRUTTURA DELLA TESI 5
dotto consentendo di semplificare il CS. Successivamente viene dimostrato che
il problema di identificazione ammette soluzione se e solo se il CS è ammissi-
bile e viene enunciato nuovamente il problema di identificazione associando una
funzione obiettivo all’insieme dei vincoli. Quindi vengono illustrati tre esempi
di applicazione della procedura. Infine vengono introdotte alcune estensioni alla
procedura di base che consistono nell’aggiungere nuovi vincoli al CS, sfruttando
delle informazioni addizionali sulla struttura della rete (proprietà e classi di reti
P/T) o sulla marcatura iniziale (GMEC), e risolvere così un CS aumentato.
Nel capitolo 5 vengono presentati i due approcci per ridurre il numero di posti,
proposti in [13]: la tecnica della pre-riduzione e la tecnica della post-riduzione. I
due approcci sono stati proposti per eliminare lo svantaggio più importante della
procedura presentata nel capitolo precedente, cioè la richiesta di una rete con un
numero di posti pari alla cardinalità di D. Prima viene presentata la tecnica di
pre-riduzione che, come suggerisce il nome, viene applicata prima di calcolare la
soluzione del problema di programmazione. Viene presentato un risultato genera-
le che consente di controllare se il numero di posti richiesto è minimo. A tal scopo
si introduce il concetto di partizionamento a blocchi dell’insieme D, si caratteriz-
za il numero di posti in maniera tale che esso sia pari al numero di blocchi di tale
partizione e si determina se una partizione è minima. Siccome il numero di queste
partizioni è spesso un numero molto grande, questo procedimento non viene mai
utilizzato. Nella pratica la pre-riduzione viene effettuata determinando una parti-
zione di D, sfruttando delle informazioni aggiuntive sulla rete. Questa partizione,
come verrà mostrato, non è necessariamente quella minima. Si può ulteriormente
ridurre il numero di posti e di vincoli come spiegato nel capitolo 4. Successiva-
mente viene presentata la tecnica di post-riduzione che, come suggerisce il nome,
viene applicata dopo aver calcolato la soluzione del problema di programmazio-
ne. Prima si controlla se la rete ottenuta ha posti ridondanti che possono essere
rimossi senza modificare il linguaggio generato L. A tal scopo viene definito il
concetto di hitting set. Quindi per verificare se il numero di posti è minimo si
ricorre alla nozione di hitting set minimo. Viene presentato un algoritmo basato
sulla programmazione intera per calcolare l’hitting set minimo. Infine vengono ri-
portati due esempi di post-riduzione, dei quali il secondo dimostra che non sempre
questa tecnica garantisce di trovare la rete col numero minimo di posti.
Nel capitolo 6 vengono presentati i programmi realizzati con Matlab che con-
sentono di eseguire automaticamente la procedura di identificazione illustrata nei
capitoli 4 e 5. Si comincia con una presentazione generale del lavoro svolto me-
diante l’ausilio di uno schema a blocchi che illustra i vari programmi realizzati,
gli ingressi, le uscite e i collegamenti tra i programmi. Poi viene descritto ogni
singolo programma realizzato. Nell’ordine, per ciascun programma vengono ri-
6 CAPITOLO 1. INTRODUZIONE
portati la sintassi della relativa funzione, la lista degli argomenti di ingresso, la
lista degli argomenti di uscita, la descrizione sintetica dell’algoritmo nei suoi vari
passi e un esempio di applicazione, con relativa spiegazione, tratto dalla finestra
dei comandi di Matlab. Sono stati realizzati 6 programmi. Il primo calcola il lin-
guaggio massimale generato dalla rete di cui abbiamo a disposizione una struttura
di partenza, cioè il linguaggio costituito dalle stringhe di massima lunghezza, non
superiore a k. Il secondo costruisce gli insiemi E e D a partire dal linguaggio
massimale. Il terzo costruisce il CS a partire da E e D, eventualmente sfruttan-
do le informazioni sulla rete che consentono di applicare una pre-riduzione. Il
quarto identifica la rete P/T risolvendo il problema di programmazione lineare de-
finito con l’ausilio di GLPK, eventualmente sfruttando informazioni addizionali
sulla rete. Il quinto estrae la rete ridotta applicando una post-riduzione. Infine
il sesto programma esegue l’intera procedura di identificazione richiamando i 5
programmi precedenti.
Nel capitolo 7 vengono mostrati degli esempi di testing dei programmi effettuati
su 4 sistemi di rete al variare di determinati parametri e vengono elencati i risultati
ottenuti. Si comincia con una presentazione generale in cui vengono specificati la
macchina su cui sono state eseguite le simulazioni e i dati più importanti ricavati
dai test, organizzati in tabelle. Questi riguardano i limiti di utilizzo di Matlab e
GLPK, i linguaggi generati nei vari passi della procedura, la complessità del pro-
blema di programmazione lineare, la variazione del numero di posti e i tempi di
computazione. Poi vengono illustrati i 4 esempi per ciascuno dei quali vengono
riportate le tabelle contenenti i dati più importanti e vengono riportati i relati-
vi commenti e le considerazioni. Il capitolo si chiude con la presentazione dei
risultati finali.
Il capitolo 8 è quello conclusivo.
In appendice si possono trovare i listati Matlab dei programmi e alcune note su
GLPK e GLPKMEX, un’interfaccia MEX di GLPK per utilizzare il software in
Matlab.
I contributi che questa tesi ha portato alla ricerca sono di natura implementativa
(sviluppo di software) e sperimentale:
• Un primo contributo originale della tesi consiste nello sviluppo di un tool-
box Matlab per l’identificazione di una rete P/T.
• Un secondo contributo, di natura sperimentale, consiste nella dimostrazione
che i risolutori della versione 4.9 di GLPK non sono totalmente affidabili
per problemi di grandi dimensioni.
1.3. STRUTTURA DELLA TESI 7
• Un terzo contributo, anch’esso sperimentale, consiste nella dimostrazione
che la programmazione lineare riduce sensibilmente il tempo di risoluzione
di un problema di identificazione rispetto alla programmazione intera.
• Un quarto contributo sperimentale consiste nella dimostrazione che la tec-
nica di post-riduzione permette in tutti i casi trattati di estrarre una rete con
un numero di posti molto più piccolo rispetto alla rete estratta mediante la
risoluzione del problema di programmazione lineare.
8 CAPITOLO 1. INTRODUZIONE
Capitolo 2
Richiami alle reti di Petri
2.1 Introduzione
In questo capitolo viene richiamato il formalismo delle reti di Petri utilizzato nella
tesi. Facciamo riferimento a [11] per una più completa introduzione alle reti.
Le reti di Petri sono un modello di sistemi ad eventi discreti che trae origine dal
lavoro di Carl Adam Petri, un ricercatore tedesco, che nel 1962 discusse la sua tesi
di dottorato dal titolo “Kommunication mit Automaten”, in cui presentava questo
nuovo modello logico che in seguito avrebbe appunto preso il suo nome.
Un sistema ad eventi discreti (SED) è un sistema il cui comportamento dinamico
è caratterizzato dall’accadimento asincrono di eventi che individuano lo svolgi-
mento di attività di durata non necessariamente nota. Formalmente, un sistema ad
eventi discreti è caratterizzato da:
• Un insieme E degli eventi accadibili.
• Uno spazio di stato costituito da un insieme discreto X.
• Un’evoluzione dello stato regolata dagli eventi: lo stato evolve nel tem-
po solo in dipendenza dell’accadimento di eventi asincroni, appartenenti
all’insieme E.
L’equazione che descrive l’evoluzione dello stato a partire dallo stato iniziale x0 è
xk+1 = δ(xk, ek)
9
10 CAPITOLO 2. RICHIAMI ALLE RETI DI PETRI
dove
• xk+1 è lo stato del sistema dopo l’accadimento dell’evento k-esimo.
• ek è il k-esimo evento accaduto dall’istante iniziale considerato, che fa
transire lo stato da xk a xk+1.
• δ : X × E −→ X è la funzione di transizione di stato.
I sistemi ad eventi discreti si dividono in due grandi famiglie: i modelli logici e i
modelli temporizzati, a seconda del tipo di traccia (o traiettoria) degli eventi adot-
tata. Nei modelli logici la traccia degli eventi è costituita semplicemente da una
sequenza di eventi {e1, e2, ...}, in ordine di occorrenza, senza alcuna informazione
circa i tempi di occorrenza degli eventi. Dato uno stato iniziale x0, la traiettoria
dello stato verrà costruita nel tempo come la sequenza di stati {x0, x1, x2, ...} ri-
sultanti dall’accadimento della sequenza di eventi, ma non è possibile specificare
gli istanti di tempo in cui avvengono le transizioni di stato. Nei modelli tem-
porizzati, invece, la traccia degli eventi è costituita da una sequenza di coppie
{(e1, τ1), (e2, τ2), ...} dove ogni elemento ei è accoppiato al suo tempo di accadi-
mento τi, eventualmente stocastico. Dato uno stato iniziale x0, la traiettoria dello
stato sarà evidentemente ancora la sequenza di stati {x0, x1, x2, ...} risultanti dal-
l’accadimento della sequenza di eventi. In questo caso però si sa che le transizioni
di stato avvengono negli istanti di occorrenza degli eventi. I modelli logici ren-
dono agevole lo studio delle proprietà qualitative del sistema e consentono quindi
di effettuare l’analisi strutturale di un SED, mentre i modelli temporizzati per-
mettono di studiare i diversi comportamenti nel tempo del sistema, pertanto sono
indispensabili qualora si voglia effettuare l’analisi prestazionale di un SED. In
ogni caso, si può concludere che un modello ad eventi discreti costituisce sempre
una descrizione matematica finita dell’insieme infinito di tracce che rappresentano
il comportamento di un sistema ad eventi discreti ad un certo livello di astrazione.
Le reti di Petri rappresentano uno degli strumenti più efficaci nell’analisi di tutto
quel ramo dell’automatica che si occupa di studiare i sistemi ad eventi discreti.
Esse si dividono in logiche e temporizzate. Queste ultime si dividono a loro vol-
ta in deterministiche e stocastiche. In questa tesi verranno trattate le reti di Petri
logiche o reti posto/transizione (o reti P/T), che consistono in un modello logico
che non consente di rappresentare la temporizzazione degli eventi, ma solo l’or-
dine con cui essi si verificano. Fra i vari modelli ad eventi discreti, le reti di Petri
hanno un’importanza predominante a causa di vari fattori:
2.2. STRUTTURA DELLE RETI P/T 11
• Forniscono un formalismo grafico e matematico per la modellazione dei
SED.
• Permettono di dare una rappresentazione compatta in termini di spazio di
stato (rappresentano SED con un numero infinito di stati, mediante un grafo
con un numero finito di nodi).
• Permettono di rappresentare esplicitamente il concetto di concorrenza, cioè
di attività che possono venire svolte parallelamente.
• Consentono una rappresentazione modulare; cioè se un sistema è compo-
sto da più sottosistemi che interagiscono tra loro, è generalmente possibile
rappresentare ciascun sottosistema come una semplice sottorete e poi, me-
diante operatori di rete, unire le varie sottoreti per ottenere il modello del
sistema complessivo.
2.2 Struttura delle reti P/T
In questa sezione viene definita la struttura algebrica e grafica delle reti P/T.
Una rete P/T è un grafo bipartito, orientato e pesato. I due tipi di vertici sono
detti: posti (rappresentati da cerchi) e transizioni (rappresentati da barre o da ret-
tangoli). Gli archi, che devono essere orientati, connettono i posti alle transizioni
e viceversa.
Definizione 2.2.1. Una rete P/T è una struttura N = (P, T, Pre, Post) dove:
• P = {p1, p2, ..., pm} è l’insieme degli m posti.
• T = {t1, t2, ..., tn} è l’insieme delle n transizioni.
• Pre : P × T −→ N: è la funzione di pre-incidenza che specifica gli archi
diretti dai posti alle transizioni (detti archi “pre”) e viene rappresentata
mediante una matrice m× n.
• Post : P ×T −→ N: è la funzione di post-incidenza che specifica gli archi
diretti dalle transizioni ai posti (detti archi “post”) e viene rappresentata
mediante una matrice m× n. ¥
Si suppone che P∩T = ∅ , cioè posti e transizioni sono insiemi disgiunti e che P∪
T 6= ∅ , cioè la rete è costituita da almeno un posto o da una transizione. Le matrici
12 CAPITOLO 2. RICHIAMI ALLE RETI DI PETRI
Pre e Post sono delle matrici di interi non negativi. Si denota con Pre(·, t)
(Post(·, t)) la colonna della matrice Pre (Post) relativa alla transizione t, e con
Pre(p, ·) (Post(p, ·)) la riga della matrice Pre relativa al posto p. Le matrici Pre
e Post possono essere compattate in un’unica matrice, detta di incidenza.
Definizione 2.2.2. Data una rete N = (P, T, Pre, Post), con m posti ed n tran-
sizioni, la matrice di incidenza C : P × T −→ Z è la matrice m × n definita
come:
C = Post− Pre,
cioè il generico elemento di C vale C(p, t) = Post(p, t)− Pre(p, t). ¥
Data C potrei non essere in grado di ricostruire perfettamente il grafo, mentre date
le matrici Pre e Post ciò è sempre possibile.
Un esempio chiarirà questi concetti.
Esempio 2.2.1. In Figura 2.1 è rappresentata la rete N = (P, T, Pre, Post) con
insieme dei posti P = {p1, p2, p3, p4} e insieme delle transizioni T = {t1, t2, t3,
t4, t5}. Le matrici Pre e Post valgono:
Pre =


1 1 0 0 0
0 0 1 1 0
0 0 0 0 1
0 0 0 0 1


, Post =


1 0 0 0 1
0 2 0 0 0
0 0 1 0 0
0 0 0 1 0


.
La matrice di incidenza vale:
C =


0 −1 0 0 1
0 2 −1 −1 0
0 0 1 0 −1
0 0 0 1 −1


.
Si noti che Post(p2, t2) = 2 e dunque vi sono due archi che vanno dalla transi-
zione t2 al posto p2. Nella figura, invece di rappresentare i due archi è usata una
notazione semplificata che consiste nel rappresentare un solo arco avente per eti-
chetta un numero (2 in questo caso) che indica la sua molteplicità. Si noti anche
che tra il posto p1 e la transizione t1 vi è sia un arco “pre” che un arco “post”. Si
dice che p1 e t1 costituiscono un cappio, cioè un ciclo orientato costituito da una
sola transizione e da un solo posto. In questo caso la somma algebrica di Pre e
2.3. MARCATURA E SISTEMA DI RETE 13
 
t1 t2 
t3 
t4 
t5 
2 
p1 p2 
p3 
p4 
Figura 2.1: Una rete posto-transizione.
Post determina un elemento C(p1, t1) = 0, cioè dall’esame della sola C non è
possibile rilevare che vi sono archi tra questi due vertici. ¤
Infine, data una transizione si definiscono i seguenti sistemi di posti:
•
t = {p ∈ P | Pre(p, t) > 0} : è l’insieme dei posti in ingresso a t.
t
• = {p ∈ P | Post(p, t) > 0} : è l’insieme dei posti in uscita da t.
•p = {t ∈ T | Post(p, t) > 0} : è l’insieme delle transizioni in ingresso a p.
p• = {t ∈ T | Pre(p, t) > 0} : è l’insieme delle transizioni in uscita da p.
Ad esempio nella rete in Figura 2.1 vale •t2 = {p1}, t•2 = {p2}, •p2 = {t2},
p•2 = {t3, t4}.
2.3 Marcatura e sistema di rete
In questa sezione vediamo come, aggiungendo ad una struttura di rete una mar-
catura, si ottiene una rete marcata (o sistema di rete), cioè un sistema ad eventi
discreti, di cui si studieranno le leggi che ne governano l’evoluzione dinamica e
che vedremo in seguito.
Mediante la marcatura è possibile definire lo stato di una rete P/T.
Definizione 2.3.1. Una marcatura è una funzione M : P → N che assegna ad
ogni posto un numero intero non negativo di marche (o gettoni) rappresentate
graficamente con dei pallini neri dentro i posti. ¥
Considerando l’esempio in Figura 2.1, una marcatura possibile M è M(p1) =
14 CAPITOLO 2. RICHIAMI ALLE RETI DI PETRI
 
 
 
 
 
 
t1 t2 
t3 
t4 
t5 
2 
p1 p2 
p3 
p4 (b) 
t1 t2 
t3 
t4 
t5 
2 
p1 p
p3 
p4 (a) 
Figura 2.2: Evoluzione di una rete marcata. (a) Marcatura iniziale. (b) Marcatura
raggiunta dopo lo scatto di t2.
1,M(p2) = M(p3) = M(p4) = 0, come mostrato in Figura 2.2(a). Un’altra
marcatura possibile è quella mostrata in Figura 2.2(b), dove M(p1) = 0,M(p2) =
2,M(p3) = M(p4) = 0.
Definizione 2.3.2. Una rete N con una marcatura iniziale M0 è detta rete marcata
o sistema di rete, e viene indicata come 〈N,M0〉. ¥
Una rete marcata è in effetti un sistema ad eventi discreti a cui è associato un
comportamento dinamico come vedremo nella prossima sezione.
2.4 Abilitazione e scatto
In questa sezione vengono definiti l’abilitazione e lo scatto di una transizione.
2.4. ABILITAZIONE E SCATTO 15
Definizione 2.4.1. Una transizione t è abilitata dalla marcatura M se
M > Pre(·, t),
cioè se ogni posto p ∈ P della rete contiene un numero di marche pari o superiore
a Pre(p, t). Per indicare che t è abilitata da M si scrive M [t〉 . Per indicare che
t
′ non è stata abilitata da M si scrive ¬M [t′〉. ¥
Una transizione che non possiede archi in ingresso è detta transizione sorgente ed
è sempre abilitata.
Definizione 2.4.2. Una transizione t abilitata da una marcatura M può scatta-
re. Lo scatto di t rimuove Pre(p, t) marche da ogni posto p appartenente a P e
aggiunge Post(p, t) in ogni posto p appartenente a P , determinando una nuova
marcatura M ′. Cioè vale:
M ′ = M − Pre(·, t) + Post(·, t) = M + C(·, t).
Per indicare che lo scatto di t da M determina la marcatura M ′ si scrive M [t〉M ′.
¥
Dall’ispezione visiva di una rete marcata è facile rendersi conto se una transizione
t è abilitata: occorre che ogni posto in ingresso alla transizione, cioè ogni posto
p ∈ •t, abbia un numero di marche pari o superiore agli archi “pre” che vanno
dal posto alla transizione. Nella rete marcata in Figura 2.2(a), l’insieme delle
transizioni abilitate è {t1, t2}. Nella rete marcata in Figura 2.2(b), l’insieme delle
transizioni abilitate è {t3, t4}. La marcatura in Figura 2.2(b) è stata ottenuta dalla
marcatura in Figura 2.2(a) con lo scatto di t2.
Definizione 2.4.3. Una sequenza di transizioni σ = tj1tj2 ...tjr ∈ T ∗1 è abilitata
da una marcatura M se: la transizione tj1 è abilitata da M e il suo scatto porta
a M1 = M + C(·, tj1); la transizione tj2 è abilitata da M1 e il suo scatto porta a
M2 = M1 + C(·, tj2), ecc. Una sequenza abilitata σ viene anche detta sequenza
di scatto e ad essa corrisponde la traiettoria:
M [tj1〉M1[tj2〉M2...[tjr〉Mr.
¥
Per indicare che la sequenza σ è abilitata da M si scrive M [σ〉. Per indicare che
lo scatto di σ da M determina la marcatura M ′ si scrive M [σ〉M ′.
1T ∗ indica l’insieme di tutte le sequenze (di lunghezza 0, 1, 2, ecc.), composte dalla
concatenazione di elementi di T .