Siguiente: Problema de acceso generalizado Un nivel arriba: Complejidad en redes de Anterior: Problemas de acotación

Problemas de acceso

Para una r.P.g. R=(L,T,A,p) y un marcado inicial $\mbox{\bf m}_0$, consideremos los problemas siguientes: Problema de acceso (PA):


Instancia:

Solución:




Problema de acceso a submarcados (PAS):


Instancia:

Solución:




Problema de acceso a cero (PA0): PA con la instancia $\mbox{\bf0}$. Problema de acceso a cero en un lugar dado (PA0L):


Instancia:

Solución:




Se ve directamente que valen las reducibilidades siguientes:

$$\begin{array}{rcl} \mbox{\bf PA0} &\stackrel{\mbox{\it insta... ...x{\it instancia}}{\hookrightarrow}& \mbox{\bf PAS} \end{array}$$

Para completar el diagrama de reducibilidades veamos lo siguiente:

PAS se reduce a PA0:

Dada una instancia de PAS consistente de una red R=(L,T,A,p), un marcado inicial $\mbox{\bf m}_0$, un subconjunto $L_1\subset L$ de lugares y un vector de (sub)-marcado $\mbox{\bf m}_1\in R^{L_1}$ la transformaremos en una instancia equivalente de PA0. Introducimos como elementos nuevos

$$\begin{eqnarray*}l_0 &:&\mbox{\rm\begin{minipage}[t]{20em} un nuevo lugar tal q... ...y con la arista de peso 1, $(\lambda_l,t_l)$ . \end{minipage}} \end{eqnarray*}$$

Se ve que la instancia transformada tiene una solución positiva en PA0 si y sólo si la instancia dada tiene también una solución positiva en PAS.

PA0 se reduce a PA0L:

Dada una instancia de PA0 consistente de una red R=(L,T,A,p) y un marcado inicial $\mbox{\bf m}_0$, añadimos un lugar nuevo $\lambda_0$ tal que en todo marcado accesible $\mbox{\bf m}'$ se tenga

$$\left[\mbox{\bf m}'\right]_{\lambda_0}=\sum_{l\not=\lambda_0}\left[\mbox{\bf m}'\right]_{l}.$$

Así tendremos que la instancia dada da respuesta positiva con PA0 si y sólo si la instancia modificada la da con PA0L para $\lambda_0$. Para esto, inicialmente se le asigna a $\lambda_0$ una marca de $\sum_{l\in L}\left[\mbox{\bf m}_0\right]_{l}$. Luego, para cada transición $t\in T$ calculamos el cambio de marcas cuando se dispara t:

$$\Delta_t=\sum_{l\in L}\left(\left[\mbox{\bf s}_t\right]_l-\left[\mbox{\bf e}_t\right]_l\right).$$

Dependiendo de este valor se hacen conexiones a $\lambda_0$:

$$\begin{eqnarray*}\Delta_t \geq 0 &\Rightarrow& \mbox{\rm se incorpora la arista ... ...orpora la arista $(\lambda_0,t)$\space con peso $-\Delta_t$ ,} \end{eqnarray*}$$

Así pues, los cuatro problemas anteriores de acceso son reducibles unos a otros.




Siguiente: Problema de acceso generalizado Un nivel arriba: Complejidad en redes de Anterior: Problemas de acotación