Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Gianmaria De Tommasi » 8.Proprietà comportamentali delle reti di Petri


Sommario della lezione

  • Proprietà comportamentali delle reti di Petri
  • Raggiungibilità
  • Limitatezza
  • Conservatività
  • Ripetitività
  • Reversibilità
  • Vivezza

Raggiungibilità

Problema
“Dato un sistema rete \langle N\,,\mathbf{m}_0\rangle e una generica marcatura \mathbf{m}, è possibile raggiungere \mathbf{m} da \mathbf{m}_0 ?”

Il problema è decidibile se R\bigl(N\,,\mathbf{m}_0\bigr) ha cardinalità finita e si può risolvere utilizzando il grafo di raggiungibilità

È stato dimostrato che il problema è decidibile anche nel caso in cui R\bigl(N\,,\mathbf{m}_0\bigr) abbia cardinalità infinita, ma l’algoritmo che risolve il problema ha una tale complessità da non poter essere considerato nella pratica.

Nella pratica, quando R\bigl(N\,,\mathbf{m}_0\bigr) ha cardinalità infinita, il problema è semi-decidibile.

È possibile costruire stime dell’insieme R\bigl(N\,,\mathbf{m}_0\bigr) per poter studiare la raggiungibilità.

Limitatezza – Definizioni

Limitatezza

  • Dato un sistema rete \langle N\,,\mathbf{m}_0\rangle, un posto p è k-limitato se \forall\ \mathbf{m}\inR\bigl(N\,,\mathbf{m}_0\bigr) vale \mathbf{m}(p)\leq k.
  • Un posto 1-limitato si dice Safe
  • Una rete è k-limitata se ogni suo posto è k-limitato.
  • Una rete Safe è una rete 1-limitata.

Limitatezza – Risultati

Proposizione 1
Il sistema \langle N\,,\mathbf{m}_0\rangle è Limitato \iff R\bigl(N\,,\mathbf{m}_0\bigr) ha cardinalità Finita


Proposizione 2
Si consideri il sistema \langle N\,,\mathbf{m}_0\rangle e il suo grafo di copertura. Allora:

  • un posto p è k-limitato \iff per ogni nodo \mathbf{m} del grafo vale \mathbf{m}(p)\leq k\neq\omega
  • Il sistema rete è limitato \iff nessun nodo del grafo contiene il simbolo \omega (cioè il grafo di copertura è un grafo di raggiungibilità)

Conservatività – Definizione 1

Conservatività – Sistema strettamente conservativo

Un sistema rete \langle N\,,\mathbf{m}_0\rangle si dice Strettamente Conservativo se \forall\ \mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr) il numero di token non varia, vale a dire

\mathbf{1}^T\mathbf{m}=\mathbf{1}^T\mathbf{m}_0\,,\forall\ \mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr)

Conservatività – Risultati 1

Rete strettamente conservativa – Condizione sufficiente

Un sistema rete \langle N\,,\mathbf{m}_0\rangle è strettamente conservativo se \forall\ t\in T vale

\sum_p\mathbf{Pre}\bigl(p\,,t\bigr)=\sum_p\mathbf{Post}\bigl(p,,t\bigr)

Questa condizione verifica una condizione STRUTTURALE, vale a dire una condizione che non dipende da \mathbf{m}_0

Conservatività – Definizione 2

Conservatività – Sistema conservativo

Un sistema rete \langle N\,,\mathbf{m}_0\rangle si dice Conservativo se \forall\ \mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr) vale

x^T\mathbf{m}=x^T\mathbf{m}_0

con x\in\mathbb{N}^m.

Una rete conservativa è una rete in cui non varia una somma pesata dei gettoni nei posti.

Conservatività – Risultati 2

Rete conservativa – Condizione necessaria

Se un sistema \langle N\,,\mathbf{m}_0\rangle è conservativo allora il sistema è limitato.

Dimostrazione

\langle N\,,\mathbf{m}_0\rangle conservativo \Rightarrow\ \exists\ x\in\mathbb{N}^m tale che \forall\ \mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr) vale x^T\mathbf{m}=x^T\mathbf{m}_0\Rightarrow\ \forall\ i\ x_i\mathbf{m}(p_i)\leq x^T\mathbf{m}_0\Rightarrow\ \mathbf{m}(p_i)\leq\frac{x^T\mathbf{m}_0}{x_i}\Rightarrow\ \mathbf{m}(p_i)\leq\biggl\lfloor\frac{x^T\mathbf{m}_0}{x_i}\biggr\rfloor=k

Ripetitività – Definizione

Sequenza ripetitiva
Si consideri il sistema rete \langle N\,,\mathbf{m}_0\rangle. Sia \sigma una sequenza non vuota e \mathbf{m}\bigl[\sigma\rangle con \mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr). \sigma è ripetitiva se essa può essere eseguita un numero infinito di volte da \mathbf{m}, vale a dire se

\mathbf{m}\bigl[\sigma\rangle\mathbf{m}_1\bigl[\sigma\rangle\mathbf{m}_2\bigl[\sigma\rangle\mathbf{m}_3\ldots

Sistema ripetitivo
\langle N\,,\mathbf{m}_0\rangle è Ripetitivo se esiste almeno una sequenza \sigma\in L\bigl(N\,,\mathbf{m}_0\bigr) ripetitiva

Ripetitività – Risultati 1

Proposizione

Sia \sigma una sequenza di transizioni non vuota e \mathbf{m}\bigl[\sigma\rangle.
Sia \mathbf{m}\bigl[\sigma\rangle\mathbf{m}'.

\sigma è ripetitiva \iff\ \mathbf{m}'\geq\mathbf{m}

Ripetitività – Sequenze stazionarie e crescenti

Sequenza stazionarie e crescenti

Una sequenza \sigma abilitata da \mathbf{m} si dice:

  • Stazionaria se \mathbf{m}\bigl[\sigma\rangle\mathbf{m}
  • Crescente se \mathbf{m}\bigl[\sigma\rangle\mathbf{m}' con \mathbf{m}'\gneq\mathbf{m} (\mathbf{m}' deve avere almeno una componente strettamente maggiore rispetto a \mathbf{m})

Ripetitività – Risultati 2

Proposizione

\langle N\,,\mathbf{m}\rangle è Limitata \iff non ammette sequenze \sigma Ripetitive Crescenti

Proposizione

Si consideri un sistema \langle N\,,\mathbf{m}_0\rangle e il suo grafo di raggiungibilità. Una sequenza \sigma è Stazionaria \iff esiste un ciclo orientato nel grafo i cui archi formano la sequenza \sigma.

Ripetitività – Risultati 3

Proposizione

Si consideri un sistema \langle N\,,\mathbf{m}_0\rangle e il suo grafo di copertura.

\sigma è Ripetitiva \Rightarrow esiste un ciclo orientato nel grafo i cui archi formano \sigma.
\sigma è Stazionaria \Leftarrow esiste un ciclo orientato nel grafo che non passa per marcature contenenti il simobolo \omega e i cui archi formano \sigma.

Reversibilità – Definizione

Reversibilità

Un sistema rete \langle N\,,\mathbf{m}_0\rangle è REVERSIBILE se per ogni \mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr) vale \mathbf{m}_0\in R\bigl(N\,,\mathbf{m}\bigr)

Reversibilità – Risultati 1

Reversibilità – Condizione necessaria e sufficiente

Un sistema rete \langle N\,,\mathbf{m}_0\rangle è Rerversibile \iff per ogni sequenza \sigma abilitata da \mathbf{m}_0 esiste una sequenza \sigma' tale che \mathbf{m}_0\bigl[\sigma\sigma'\rangle e \sigma\sigma' è Stazionaria (cioè \mathbf{m}_0\bigl[\sigma\sigma'\rangle\mathbf{m}_0).

Reversibilità – Osservazione

Osservazione

L’esistenza solo di alcune sequenze stazionarie abilitate a partire da \mathbf{m}_0 non è sufficiente per la reversibilità.

Esempio

\sigma_1=t_1t_2 e \sigma_2=t_2t_1 sono sequenze stazionarie ma la rete non è reversibile (si consideri lo scatto di t_3)


Reversibilità – Risultati 2

Reversibilità – Condizione necessaria e sufficiente per reti con insieme di raggiungibilità a cardinalità finita

Un sistema rete \langle N\,,\mathbf{m}_0 ) Limitato è Reversibile \iff il grafo di raggiungibilità è Fortemente Connesso.

Un grafo orientato si dice Fortemente Connesso se per ogni coppia di nodi v e v' esiste un cammino orientato da v a v'

Reversibilità – Risultati 3

Reversibilità – Condizione necessaria per reti con insieme di raggiungibilità a cardinalità infinita.

Se un sistema rete \langle N\,,\mathbf{m}_0) è Reversibile \Rightarrow ogni Componente Assorbente del grafo di copertura contiene un nodo \mathbf{m}_\omega\geq\mathbf{m}_0

Una componente assorbente di un grafo è un insieme di nodi e archi che non ha archi verso altri nodi al difuori della componente stessa.

Reversibilità – Esempio

Entrambe le reti hanno delle componenti assorbenti tali che \mathbf{m}_\omega\geq\mathbf{m}_0 ma in un caso la rete è reversibile mentre nell’altro caso no! (la condizione è solo necessaria)


Vivezza di una transizione – Definizione

Vivezza di una transizione
La vivezza di una transizione implica la possibilità che essa possa sempre eventualmente scattare, indipendentemente dalla marcatura raggiunta dalla rete.

Definizione
Dato un sistema rete \langle N\,,\mathbf{m}_0\rangle, una transizione t si dice:

  • Morta, se \nexists\ \mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr) tale che \mathbf{m}\bigl[t\rangle
  • Quasi-Viva, se \exists\ \mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr) tale che \mathbf{m}\bigl[t\rangle
  • Viva, se \forall\ \mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr) t è Quasi Viva in \langle N\,,\mathbf{m}\rangle

Vivezza – Esempio

Esempio (figura a lato)

t_1 e t_2 è Quasi Viva
t_4 è Morta
t_3 è Viva


Vivezza di una una rete – Definizione

Vivezza di un sistema rete

Un sistema rete \langle N\,,\mathbf{m}_0), è:

  • Morto se tutte le transizioni sono Morte
  • Non Quasi-Vivo contiene transizioni Morte e Quasi Vive
  • Quasi Vivo se tutte le transizioni sono Quasi Vive
  • Vivo se tutte le transizioni sono Vive

Marcatura morta e sistema bloccante

Dato un sistema rete \langle N\,,\mathbf{m}_0\rangle, sia \mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr). \mathbf{m} si dice Marcatura Morta se \nexists\ t tale che \mathbf{m}\bigl[t\rangle, cioè se \langle N\,,\mathbf{m}\rangle è MORTA.

Un sistema \langle N\,,\mathbf{m}_0\rangle è Bloccante se esiste almeno una marcatura morta.

Se \langle N\,,\mathbf{m}_0\rangle è bloccante \Rightarrow \langle N\,,\mathbf{m}_0\rangle non è vivo.

Marcatura morta – Esempio

Questa rete è bloccante benchè abbia tutte le
transizioni Quasi-Vive che potrebbero scattare
un numero infinito di volte.

Questa rete presenta una sincronizzazione a valle di una scelta.


Vivezza – Risultati 1

Vivezza per reti con insieme di raggiungibilità a cardinalità finita

Si consideri un sistema rete \langle N\,,\mathbf{m}_0\rangle Limitato e il suo grafo di raggiungibilità. Allora:

  • La transizione t è Morta \iff t non compare nel grafo
  • La transizione t è Quasi Viva \iff t compare nel grafo
  • La transizione t è Viva \iff esiste un arco t uscente da ogni componente assorbente del grafo
  • La marcatura \mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr) è Morta \iff non ci sono archi uscenti dal nodo \mathbf{m} del grafo

Vivezza – Risultati 2

Vivezza per reti con insieme di raggiungibilità a cardinalità infinita

Si consideri un sistema rete \langle N\,,\mathbf{m}_0\rangle e il suo grafo di copertura. Allora:

  • La transizione t è Morta \iff t non compare nel grafo
  • La transizione t è Quasi Viva\iff t compare nel grafo
  • Se la transizione t è Viva \Rightarrow esiste un arco t uscente da ogni componente assorbente del grafo
  • Se esiste nel grafo un nodo \mathbf{m}_\omega\geq_\omega\mathbf{m} da cui Non escono archi \Rightarrow \mathbf{m} è Morta

Proprietà comportamentali – Osservazione

Osservazione

Limitatezza, reversibilità e vivezza sono tre proprietà Indipendenti.

I materiali di supporto della lezione

Capitolo 4, paragrafo 4.3.3 (fino a pagina 182) da Di Febbraro-Giua.

Decidibilità

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion