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

Problemas de acotación

Sea R una r.P.g. y sea $\mbox{\bf m}_0$ un marcado inicial. Un árbol de recubrimiento $\mbox{\bf A}(R,\mbox{\bf m}_0)$ describe las ``computaciones'' derivables por la red a partir del marcado inicial. Formalmente este árbol se define de manera inductiva:

1.

La raíz se etiqueta con el marcado inicial $\mbox{\bf m}_0$.

2.

Si $\mbox{\bf n}$ es un nodo ya construído con etiqueta $\mbox{\bf m}_{\mbox{\bf n}}$ pueden ocurrir cuatro casos:

(a)

Ninguna transición es disparable con $\mbox{\bf m}_{\mbox{\bf n}}$: En este caso, $\mbox{\bf n}$ es una hoja de terminación muerta.

(b)

El marcado actual se ha repetido previamente: Si existe un ancestro $\mbox{\bf n}_1$ de $\mbox{\bf n}$ con la misma etiqueta, es decir, tal que $\mbox{\bf m}_{\mbox{\bf n}_1}=\mbox{\bf m}_{\mbox{\bf n}}$, entonces $\mbox{\bf n}$ es una hoja de terminación ciclada-$\lambda$, y se coloca un apuntador-$\lambda$ de $\mbox{\bf n}$ a $\mbox{\bf n}_1$.

(c)

El marcado actual cubre propiamente a uno aparecido previamente: Si existe un ancestro $\mbox{\bf n}_1$ de $\mbox{\bf n}$ tal que $\mbox{\bf m}_{\mbox{\bf n}_1}<\mbox{\bf m}_{\mbox{\bf n}}$, entonces $\mbox{\bf n}$ es una hoja de terminación ciclada-$\omega$, y se coloca un apuntador-$\omega$ de $\mbox{\bf n}$ a $\mbox{\bf n}_1$.

(d)

En cualquier otro caso, para cada transición t disparable se le asocia a $\mbox{\bf n}$ un nodo hijo etiquetado por el marcado $\mbox{\bf m}_{\mbox{\bf n}}-\mbox{\bf e}_t+\mbox{\bf s}_t$. El arco hacia el hijo se etiqueta con la transición t.

Las siguientes observaciones son inmediatas

1.

Dados R y $\mbox{\bf m}_0$, $\mbox{\bf A}(R,\mbox{\bf m}_0)$ es efectivamente constructible.

2.

Cada nodo en $\mbox{\bf A}(R,\mbox{\bf m}_0)$ tiene a lo sumo un número finito de hijos. Luego, si el árbol fuera infinito, necesariamente ha de tener ramas infinitas.

3.

Por lo anterior, se tiene que todo árbol $\mbox{\bf A}(R,\mbox{\bf m}_0)$ es finito.

4.

Si $\mbox{\bf m}$ aparece como etiqueta de un nodo entonces cae en $\mbox{\it Ac}_R(\mbox{\bf m}_0)$.

Proposición: Se puede decidir efectivamente si acaso la red R es acotada. Demostración: La red R es acotada si y sólo si $\mbox{\bf A}(R,\mbox{\bf m}_0)$ no posee hojas de terminación ciclada-$\omega$.


Consecuencias: Con técnicas similares a la anterior resulta que los conceptos siguientes son todos efectivamente decidibles:

1.

Disparabilidad potencial de transiciones.

2.

Para cada transición t, la mortalidad-t de marcados.

3.

Disparabilidad infinita de una transición.

4.

Para cada lugar l, el acceso a marcados que lo hagan asumir marcas positivas (llegadas de estafetas).

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