Considere uma rede de Petri marcada, P R=\left(P, T, A, W, m_{0}\right), onde:
  • P=\left\{p_{1}, p_{2}, p_{3}, p_{4}\right\};
  • \mathrm{T}=\left\{\mathrm{t}_{0}, \mathrm{t}_{1}, \mathrm{t}_{2}, \mathrm{t}_{3}, \mathrm{t}_{4}\right\} ;
  • A=\left\{\left(p_{1}, t_{0}\right),\left(p_{1}, t_{1}\right),\left(p_{1}, t_{3}\right),\left(p_{2}, t_{2}\right),\left(p_{2}, t_{3}\right),\left(p_{3}, t_{4}\right),\left(p_{4}, t_{2}\right),\left(t_{1}, p_{2}\right),\left(t_{2}, p_{3}\right),\left(t_{3}, p_{1}\right),\left(t_{4}, p_{1}\right),\left(t_{4}, p_{4}\right)\right\} ;
  • É ordinária;
  • m_{0}=\left[\begin{array}{llll}1 & 0 & 0 & 2\end{array}\right]^{\top}.
Determine:
a) A Rede de Petri marcada.
b) Matriz de incidência.
c) Determine a árvore de alcançabilidade a partir de mo.
d) Verifique se é possível executar a seguinte sequência de disparos: t_{1} t_{2} t_{4} t_{1} t_{2} t_{4} t_{1} t_{2} t_{4} t_{0}. Caso seja possível, encontre a marcação alcançada após os disparos.
e) A marcação m=\left[\begin{array}{llll}1 & 0 & 1 & 1\end{array}\right]^{\top} é alcançável? Justifique.
f) Discuta se a rede é limitada e segura.
g) Discuta se a rede é viva.
h) EmPR, se \operatorname{Pos}\left(\mathrm{t}_{4}, \mathrm{p}_{4}\right)=2, encontre a árvore de alcançabilidade.

Passo 1

O enunciado nos dá uma Rede de Petri ordinária \mathit{PR}=(P,T,A,W,m_{0}) com P=\{p_{1},p_{2},p_{3},p_{4}\}, T=\{t_{0},t_{1},t_{2},t_{3},t_{4}\},
arcos
A=\{(p_{1},t_{0}),(p_{1},t_{1}),(p_{1},t_{3}),(p_{2},t_{2}),(p_{2},t_{3}),(p_{3},t_{4}),(p_{4},t_{2}),(t_{1},p_{2}),(t_{2},p_{3}),(t_{3},p_{1}),(t_{4},p_{1}),(t_{4},p_{4})\}
todos com peso 1, e marcação inicial
m_{0}=\begin{pmatrix}1\\\ 0\\\ 0\\\ 2\end{pmatrix}.
Precisamos determinar:
a) a própria rede marcada (pre/post-incidências e m_{0});
b) a matriz de incidência C;
c) a árvore de alcançabilidade a partir de m_{0};
d) se a sequência t_{1}\,t_{2}\,t_{4}\,t_{1}\,t_{2}\,t_{4}\,t_{1}\,t_{2}\,t_{4}\,t_{0} é executável e, em caso afirmativo, sua marcação resultante;
e) se m=[1\;0\;1\;1]^{\top} é alcançável;
f) se a rede é limitada e segura;
g) se a rede é viva;
h) supondo agora W(t_{4},p_{4})=2, refazer a árvore de alcançabilidade.

Passo 2

Construímos as matrizes de pré-incidência \mathit{Pre} e pós-incidência \mathit{Post}. Indexamos as linhas por p_{1},p_{2},p_{3},p_{4} e as colunas por t_{0},t_{1},t_{2},t_{3},t_{4}.
Pré-incidência W^{-}:
\mathit{Pre}= \begin{pmatrix} 1 & 1 & 0 & 1 & 0\\\\ 0 & 0 & 1 & 1 & 0\\\\ 0 & 0 & 0 & 0 & 1\\\\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}
Pós-incidência W^{+}:
\mathit{Post}= \begin{pmatrix} 0 & 0 & 0 & 1 & 1\\\\ 0 & 1 & 0 & 0 & 0\\\\ 0 & 0 & 1 & 0 & 0\\\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}
E a marcação inicial é
m_{0}=\begin{pmatrix}1\\\ 0\\\ 0\\\ 2\end{pmatrix}.

Passo 3

A matriz de incidência é
C = \mathit{Post}-\mathit{Pre}= \begin{pmatrix} -1 & -1 & 0 & 0 & 1\\\\ 0 & 1 & -1 & -1 & 0\\\\ 0 & 0 & 1 & 0 & -1\\\\ 0 & 0 & -1 & 0 & 1 \end{pmatrix}.

Passo 4

Construímos a árvore de alcançabilidade partindo de m_{0}=(1,0,0,2):
  1. Em m_{0} só estão habilitados t_{0} e t_{1}.
  • Disparando t_{0} obtemos m_{1}=m_{0}+C(:,t_{0})=(0,0,0,2), onde nenhum disparo é possível (folha).
  • Disparando t_{1} obtemos m_{2}=m_{0}+C(:,t_{1})=(0,1,0,2).
  1. Em m_{2} t_{2} está habilitado:
    m_{3}=m_{2}+C(:,t_{2})=(0,0,1,1).
  2. Em m_{3} t_{4} está habilitado:
    m_{4}=m_{3}+C(:,t_{4})=(1,0,0,2), que é igual a m_{0}.
Logo, a árvore tem um ramo morto em m_{1} e um ciclo m_{0}\to m_{2}\to m_{3}\to m_{0}.

Passo 5

A sequência
\sigma = t_{1}\,t_{2}\,t_{4}\,t_{1}\,t_{2}\,t_{4}\,t_{1}\,t_{2}\,t_{4}\,t_{0}
faz três voltas no ciclo t_{1}t_{2}t_{4} (retornando a m_{0}) e depois dispara t_{0}, chegando a
m = m_{0} + 3\,(C(:,t_{1})+C(:,t_{2})+C(:,t_{4})) + C(:,t_{0}) = (0,0,0,2).
Como todos os disparos no caminho são possíveis, \sigma é executável e produz \begin{pmatrix}0\\\ 0\\\ 0\\\ 2\end{pmatrix}.

Passo 6

As marcações alcançadas são apenas m_{0},m_{1},m_{2},m_{3}. A marcação \displaystyle m=(1,0,1,1)^{\top} não aparece nesse conjunto, logo não é alcançável.

Passo 7

No conjunto de todas as marcações alcançadas, nenhum lugar ultrapassa 2 tokens, logo a rede é limitada. Mas como em m_{0} 2 tokens em p_{4}, ela não é segura (segura exigiria no máximo 1 token em cada lugar).

Passo 8

A rede não é viva, pois existe a marcação m_{1}=(0,0,0,2) em que nenhuma transição está habilitada. Além disso, t_{0} dispara uma vez e leva ao modo morto.

Passo 9

Se mudamos o peso de (t_{4},p_{4}) para 2, então cada disparo de t_{4} em vez de devolver 1 token a p_{4} devolve 2. No ciclo t_{1}t_{2}t_{4} esse lugar cresce indefinidamente, gerando uma árvore de alcançabilidade infinita. Em particular, os nós sucessivos têm marcações
(1,0,0,2)\to(0,1,0,2)\to(0,0,1,1)\to(1,0,0,3)\to\cdots
com p_{4} aumentando sem limite.

Resposta

a) A Rede de Petri marcada vem dada pelos conjuntos
P=\{p_{1},p_{2},p_{3},p_{4}\},\quad T=\{t_{0},t_{1},t_{2},t_{3},t_{4}\},
arcos em A com pesos unitários e marcação inicial \displaystyle m_{0}=(1,0,0,2)^{\top}.
b) A matriz de incidência é
C=\begin{pmatrix} -1 & -1 & 0 & 0 & 1\\\\ 0 & 1 & -1 & -1 & 0\\\\ 0 & 0 & 1 & 0 & -1\\\\ 0 & 0 & -1 & 0 & 1 \end{pmatrix}.
c) A árvore de alcançabilidade tem m_{0}, um ramo morto em m_{1}=(0,0,0,2) e um ciclo m_{0}\to m_{2}\to m_{3}\to m_{0}, com
m_{2}=(0,1,0,2),\quad m_{3}=(0,0,1,1).
d) A sequência \sigma=t_{1}t_{2}t_{4}t_{1}t_{2}t_{4}t_{1}t_{2}t_{4}t_{0} é executável e leva à marcação \bigl(0,0,0,2\bigr)^{\top}.
e) m=(1,0,1,1)^{\top} não é alcançável.
f) A rede é limitada (máx.\ 2 tokens em p_{4}) mas não é segura.
g) A rede não é viva, pois leva a um modo morto em m_{1}.
h) Com W(t_{4},p_{4})=2, a árvore de alcançabilidade fica infinita, pois toda vez que t_{4} dispara, o número de tokens em p_{4} cresce sem limite.

Exercícios relacionados