Propiedades de comportamiento de la Red de Рetri

Las redes de Petri, introducidas por Carl Adam Petri a principios de los años 60, son una herramienta gráfica y matemática para el estudio de un gran número de sistemas: son uno de los formalismos más ampliamente aceptados para modelar sistemas concurrentes y distribuidos. Con una red de Petri pueden estudiarse dos tipos de propiedades: las que dependen del marcado inicial (propiedades de comportamiento) y las que sonindependientes del marcado inicial (propiedadesestructurales).

Propiedades de Comportamiento

Las principales propiedades de comportamiento son la alcanzabilidad, la acotabilidad, la vivacidad, la reversibilidad, la cobertura y la persistencia.

Definición (Marcado Alcanzable): Un marcado Mn se dice alcanzable desde un marcado si existe una secuencia de disparos que transforma M0 en Mn . Una secuencia de disparo (ver imagen superior) se denota por Ro={t1t2...tn}. En este caso, Mn es alcanzable desde M0 mediante Ro. El conjunto de todos los posibles marcados alcanzables desde M0 en una red (N, M0) se denota por R(N, M0) o simplemente por R( M0).

Definición (Problema de Alcanzabilidad): El problema de la alcanzabilidad para las redes de Petri será el problema de encontrar si M pertenece a R(M0) en una red dada (N,M0).

Definición (Red de Petri Acotada): Una red de Petri (N,M0) se dice k-acotada o acotada si el número de tokens en cada lugar no es superior a un número finito k para cualquier marcado alcanzable desde M, es decir, M(p)<= k para todo lugar p y todo marcado M que pertenece a R(M0).

Definición (Red de Petri Segura): Una red de Petri (N,M0) se dice segura si está 1-acotada.

Definición (Interbloqueo): Se dice que en una red de Petri ocurre un interbloqueo cuando se alcanza un marcado desde el que no se puede disparar ninguna transición.

Definición (Red de Petri Viva): Una red de Petri (N,M0) se dice que está viva (o equivalentemente se dice que es un marcado vivo para N) si, sea cual sea el marcado que se alcance desde , existe una secuencia disparable que permite disparar cualquier transición de la red. La vivacidad garantiza, por tanto, la ausencia de interbloqueos. Esto implica que cualquier transición es eventualmente disparable en alguna secuencia de disparo. Esta es una propiedad muy fuerte y, a menudo, muy difícil de verificar. Por ello, se habla se grados de disparo denominados niveles.

Propiedades Estructurales

Las propiedades estructurales son aquellas que dependen de la estructura topológica de las redes de Petri. Son independientes del marcado inicial en el sentido de que dichas propiedades se cumplen para cualquier marcado inicial. Son propiedades estructurales la acotabilidad estructural, la vivacidad

...