Siguiente: Ejemplo Un nivel arriba: Complejidad en redes de Anterior: Complejidad en redes de

Nociones básicas

Una red de Petri generalizada, (r.P.g.), es un sistema R=(L,T,A,p,M) tal que

• $(\{L,T\},A,p)$ es una gráfica dirigida, bipartita y ponderada, i. e.:
  • $L\cup T$ es el conjunto de vértices,
    • L es un conjunto de lugares, digamos $L=\{l_1,\ldots,l_n\}$,
    • T es un conjunto de transiciones, digamos $T=\{t_1,\ldots,t_m\}$,
  • A es el conjunto de aristas,
    
    $$A\subset (L\times T)\cup(T\times L),$$
    
    

  • $p:A\rightarrow N^+$ es una función de pesos o de incidencia. Un valor nulo de p en una arista es equivalente a la inexistencia de esa arista.
• $M:L\rightarrow N$ es una función de marcado.

Utilizaremos la terminología siguiente:

• $\mbox{\bf m}=\left[M(l_1),\ldots,M(l_n)\right]$ es el vector de marcado de la r.P.g.
• Para cada transición $t\in T$ definimos
  • Nociones de entrada de t:
    
    $$\begin{array}{rcll} \mbox{\it Ent}(t) &=& \{l\in L\vert(l,t)... ...s,p(l_n,t)\right] &\mbox{\rm : vector de entrada.} \end{array}$$
    
    

  • Nociones de salida de t:
    
    $$\begin{array}{rcll} \mbox{\it Sal}(t) &=& \{l\in L\vert(t,l)... ...ts,p(t,l_n)\right] &\mbox{\rm : vector de salida.} \end{array}$$
    
    

• Una transición $t\in T$ es disparable si
  
  $$\forall l\in \mbox{\it Ent}(t):\ M(l)\geq p(l,t),$$
  
  
  o, equivalentemente, si $\mbox{\bf m}\geq \mbox{\bf e}_t$.
• Si t es disparable, al dispararse modifica las marcas de sus lugares aledaños:
  
  $$\begin{eqnarray*}l\in \mbox{\it Ent}(t) &\Rightarrow& M'(l)=M(l)-p(l,t) \\ l\in \mbox{\it Sal}(t) &\Rightarrow& M'(l)=M(l)+p(t,l) \end{eqnarray*}$$
  
  en otras palabras, cuando t se dispara origina la modificación de marcado en la r.P.g.
  
  $$\Phi_t(\mbox{\bf m})=\mbox{\bf m}'=\mbox{\bf m}-\mbox{\bf e}_t+\mbox{\bf s}_t.$$
  
  

• Sea $M_0=\mbox{\bf m}_0$ un marcado inicial. Una sucesión de disparo es una sucesión de transiciones $\mbox{\bf t}=t_{j_1}\cdots t_{j_k}\in T^*$ tal que
  • t_j1 es disparable con el marcado inicial $M_0=\mbox{\bf m}_0$ y origina un marcado $\mbox{\bf m}_1=\Phi_{t_{j_1}}(\mbox{\bf m}_0)$.
  • Para cada $\kappa<k$, la transición $t_{j_{\kappa+1}}$ es disparable con el marcado $\mbox{\bf m}_{\kappa}$ y ha de originar al dispararse al marcado $\mbox{\bf m}_{\kappa+1}=\Phi_{t_{j_{\kappa+1}}}(\mbox{\bf m}_{\kappa})$
  En este caso el marcado $\mbox{\bf m}_k$ se dice ser el derivado po $\mbox{\bf t}$ a partir de $\mbox{\bf m}_0$. Escribamos
  
  $$\Phi_{\mbox{\bf t}}(\mbox{\bf m}_0)=\mbox{\bf m}_k.$$
  
  

• Denotamos al conjunto de sucesiones de disparo como
  
  $$S_{R}(\mbox{\bf m}_0)=\{\mbox{\bf t}\vert\mbox{\bf t}\mbox{\rm es una sucesi\'on de disparo a partir de }\mbox{\bf m}_0\}.$$
  
  

• El conjunto de vectores de marcado que se obtienen por sucesiones de disparo es el conjunto de accesibilidad,
  
  $$\mbox{\it Ac}_{R}(\mbox{\bf m}_0)=\left\{\Phi_{\mbox{\bf t}}(\mbox{\bf m}_0)\vert\mbox{\bf t}\in S_{R}(\mbox{\bf m}_0)\right\}.$$
  
  

• Dado $\mbox{\bf m}\in\mbox{\it Ac}_{R}(\mbox{\bf m}_0)$ el conjunto de sucesiones de disparo que conducen de $\mbox{\bf m}_0$ a $\mbox{\bf m}$ es
  
  $$T_{R}(\mbox{\bf m}_0,\mbox{\bf m})=\left\{\mbox{\bf t}\in S_{... ...)\vert\Phi_{\mbox{\bf t}}(\mbox{\bf m}_0)=\mbox{\bf m}\right\}.$$
  
  

• Sea $\mbox{\bf t}\in T^*$ una sucesión de transiciones. La vara de $\mbox{\bf t}$ es
  
  $$V(\mbox{\bf t})=\mathop{\rm Min}\{\mbox{\bf m}_0\vert\mbox{\bf t}\in S_{R}(\mbox{\bf m}_0).$$
  
  

• Si $\mbox{\bf t}\in S_{R}(\mbox{\bf m}_0)$ y $\mbox{\bf m}=\Phi_{\mbox{\bf t}}(\mbox{\bf m}_0)$, el cambio de marcado es
  
  $$\Delta(\mbox{\bf t})=\mbox{\bf m}-\mbox{\bf m}_0.$$
  
  

Denotemos por $\mbox{\it nil}$ a la palabra vaciía, y por $\mbox{\bf0}\in R^n$ al vector cero. Es fácil ver que la vara de toda sucesión de disparo se ajusta a las recurrencias

$$\begin{array}{rrcl} & V(\mbox{\it nil}) &=& \mbox{\bf0} \\ ... ...mbox{\bf t}),\mbox{\bf e}_t-\Delta(\mbox{\bf t})\} \end{array}$$

y, correspondientemente, el cambio de marcado satisface

$$\begin{array}{rrcl} & \Delta(\mbox{\it nil}) &=& \mbox{\bf0}... ...\Delta(\mbox{\bf t})-\mbox{\bf e}_t+\mbox{\bf s}_t \end{array}$$

Una r.P.g. R se dice ser

ordinaria

si su función de pesos asigna, en cada arista, el valor 1 si existe la arista y 0 en otro caso,

sin ciclos unitarios

si para todos $l\in L$ y $t\in T$ rigen las implicaciones

$$\begin{eqnarray*}(l,t)\in A &\Rightarrow& (t,l)\not\in A \\ (t,l)\in A &\Rightarrow& (l,t)\not\in A \end{eqnarray*}$$

restringida

si es ordinaria sin ciclos unitarios.

Para una r.P.g. R definiremos los conceptos siguientes:

marcados accesibles:

$\mbox{\bf m}$ es accesible desde el marcado inicial $\mbox{\bf m}_0$ si $\mbox{\bf m}\in\mbox{\it Ac}_{R}(\mbox{\bf m}_0)$.

marcados recubribles:

$\mbox{\bf m}$ es recubrible desde el marcado inicial $\mbox{\bf m}_0$ si

$$\exists\mbox{\bf m}_1\in\mbox{\it Ac}_{R}(\mbox{\bf m}_0):\ \mbox{\bf m}\leq \mbox{\bf m}_1.$$

lugares acotados:

$l=l_i\in L$ es un lugar acotado si

$$\exists C>0{[\forall \mbox{\bf m}\in\mbox{\it Ac}_{R}(\mbox{\bf m}_0):\vert m_i\vert\leq C]}.$$

R es acotada para un marcado inicial $\mbox{\bf m}_0$ si todos sus lugares se mantienen acotados desde ese marcado.

transiciones potencialmente disparables:

$t\in T$ es una transición potencialmente disparable con el marcado $\mbox{\bf m}$ si existe $\mbox{\bf t}\in T_{R}(\mbox{\bf m}_0,\mbox{\bf m})$ que contiene a t.

marcados muertos-t:

para una transición t el marcado $\mbox{\bf m}$ está muerto-t si t no es potencialmente disparable con el marcado $\mbox{\bf m}$,

transiciones vivas:

$t\in T$ es una transición viva en la r.P.g. R, para el marcado inicial $\mbox{\bf m}_0$, si es potencialmente disparable con todo marcado que sea accesible. La red misma R está viva con el marcado inicial $\mbox{\bf m}_0$ si toda transición está viva para ese marcado inicial.

transiciones persistentes:

$t\in T$ es una transición persistente en la r.P.g. R, para el marcado inicial $\mbox{\bf m}_0$, si la única manera de inhabilitarla es mediante su propio disparo. En otras palabras, si se cumple que $\forall t_1\in T-\{t\},\mbox{\bf m}\in\mbox{\it Ac}_{R}(\mbox{\bf m}_0)$:

$$\left(\mbox{\bf m}\geq\mbox{\bf e}_t\right)\land\left(\mbox{\... ...Rightarrow\;\mbox{\bf m}\geq \mbox{\bf e}_t+\mbox{\bf e}_{t_1}.$$

La red misma R es persistente con el marcado inicial $\mbox{\bf m}_0$ si toda transición es persistente para ese marcado inicial.

Siguiente: Ejemplo Un nivel arriba: Complejidad en redes de Anterior: Complejidad en redes de