PetrA - redes de Petri

Next: Técnicas de reducción o Up: Ecuación de estado Previous: Ecuación de estado

Condición necesaria de alcanzabilidad:

Suponga que una marca destino $M_d$ se alcanza desde una marca $M_0$ a través de una secuencia de disparos ${u_1, u_2,\ldots ,u_d}$. Escribiendo la ecuación de estado (1) para $j=1,2,\cdots,d$ y sumándolos tenemos el siguiente desarrollo:
$\displaystyle M_1$ $\textstyle =$ $\displaystyle M_0 + A^Tu_1$  
$\displaystyle M_2$ $\textstyle =$ $\displaystyle M_1 + A^Tu_2 = M_0 + A^Tu_1 + A^Tu_2$  
$\displaystyle M_3$ $\textstyle =$ $\displaystyle M_2 + A^Tu_3 = M_0 + A^Tu_1 + A^Tu_2 + A^Tu_3$  
  $\textstyle \vdots$    
$\displaystyle M_d$ $\textstyle =$ $\displaystyle M_0 + A^T\sum_{k=1}^d u_k$ (2)

La ecuación (2) puede escribirse como:
\begin{displaymath} A^Tx = \Delta M \end{displaymath} (3)

donde $\Delta M = M_d - M_0$ y $x=\sum_{k=1}^d u_k$. El vector columna $x$ de dimensión $n\times 1$, con entradas de enteros no negativos, se denimona vector de conteo de disparos. La $i$-ésima entrada de $x$ denota el número de veces que la transición $i$ se debe disparar para transformar $M_0$ en $M_d$. Además de [] se tiene que el conjunto de ecuaciones algebraicas lineales (3) tiene una solución $x$, sí y solo sí, $\Delta M$ es ortogonal a cada solución $y$ de este sistema homogeneo:
\begin{displaymath} Ay = 0 \end{displaymath} (4)

Sean $r$ el rango de $A$, y la siguiente partición de A


donde $A_{12}$ es una matriz cuadrada no singular de orden $r$. Un conjunto de $(m-n)$ soluciones linealmente independientes $y$ para (4) se puede dar como los $(m-r)$ renglones de la siguiente matriz $B_f$ de $(m-r)\times m$ elementos

\begin{displaymath} B_f = [I_{\mu} : -A_{11}^T(A_{12}^T)^{-1}] \end{displaymath}

donde $I_{\mu}$ es la matriz identidad de orden $\mu = m-r$. Note que $AB_f^T=0$, lo que quiere decir es que el espacio vectorial obtenido por los vectores renglón de $A$ es ortogonal al espacio vectorial obtenido por los vectores renglón de $B_f$. La matriz $B_f$ corresponde a la matriz de circuito fundamental para el caso de grafos marcados[]. Ahora, la condición de que $\Delta M$ sea ortogonal a cada solución para $Ay=0$ es equivalente a la siguiente condición:

\begin{displaymath} B_f\Delta M=0 \end{displaymath}

Así, si $M_d$ es alcanzable desde $M_0$, entonces el vector correspondiente $x$ de conteo de disparos, debe existir y ser válido.

PetrA | Next: Técnicas de reducción o Up: Ecuación de estado Previous: Ecuación de estado
ameneses@computacion.cs.cinvestav.mx / amilcar@synge.stp.dias.ie