Árbol de alcanzabilidad.

Dada una red de Petri (N,M₀) desde una marca inicial M₀ podemos obtener tantas nuevas marcas como transiciones habilitadas. Así, de cada nueva marca podemos obtener más marcas. Este proceso genera un árbol de marcas. Los nodos representan las marcas generadas a partir de M₀ (la raíz) y sus sucesores, y cada arco representa un disparo de una transición, la cual transforma una marca en otra.

Algunas de las propiedades que se pueden estudiar utilizando el árbol de alcanzabilidad T para una red de Petri (N,M₀) son las siguientes:

1.

Una red (N,M₀) es acotada y así R(N,M₀) es finito si y solo si $\omega$ no aparece en nigún nodo etiquetado en T.

2.

Una red (N,M₀) es libre si y solo si solo aparecen ceros y unos en las etiquetas de los nodos de T.

3.

Una transición t es muerta si y solo si no aparece como etiqueta de un arco en T.

4.

Si M es alcanzable desde M₀, entonces existe un nodo etiquetado M' tal que $M\leq M'$.