Petri

Una Red de Petri es una representación matemática o gráfica de un sistema a eventos discretos en el cual se puede describir la topología de un sistema distribuido, paralelo o concurrente

La red de Petri esencial fue definida en los años 60 por Carl Adam Petri

Son una generalización de la teoría de autómatas que permite expresar un sistema de eventos concurrentes

Una red de Petri está formada por lugares, transiciones, arcos dirigidos y marcas o fichas que ocupan posiciones dentro de los lugares

Las reglas son: Los arcos conectan un lugar a una transición así como una transición a un lugar

No puede haber arcos entre lugares ni entre transiciones

Los lugares contienen un número finito o infinito contable de marcas

Las transiciones se disparan, es decir consumen marcas de una posición de inicio y producen marcas en una posición de llegada. Una transición está habilitada si tiene marcas en todas sus posiciones de entrada

En su forma más básica, las marcas que circulan en una red de Petri son todas idénticas

Se puede definir una variante de las redes de Petri en las cuales las marcas pueden tener un color (una información que las distingue), un tiempo de activación y una jerarquía en la red

La mayoría de los problemas sobre redes de Petri son decidibles, tales como el carácter acotado y la cobertura

Para resolverlos se utiliza un árbol de Karp-Miller. Se sabe que el problema de alcance es decidible, al menos en un tiempo exponencial

Utilidad en el análisis cualitativo

Para realizar el análisis cualitativo de una red se pueden utilizar las Redes de Petri, ya que son grafos bipartidos

Según cómo analicemos la red de Petri podremos encontrarnos con:

• Análisis estructural (dependen de la estructura)
  Tienen las siguientes propiedades:
  • Repetitiva
    Existe una secuencia de disparos, incluyendo todas las transiciones, que si se pueden disparar dejan al sistema igual que al principio \Longleftrightarrow Existe un vector anulador derecho de la matriz de incidencia con todos sus términos enteros positivos
  • Conservativa
    Existe una combinación de pesos enteros positivos que si se aplican a los lugares, la suma del marcado de todos los lugares ponderados por sus pesos es invariante (siempre igual) \Longleftrightarrow Existe un vector anulador izquierdo de la matriz de incidencia con todos sus términos enteros positivos
  • Cerrojos
    Lugar o conjunto de lugares en los que las marcas que contienen no pueden disminuir, debido a que las transiciones de salida de esos lugares son también de entrada, con mayor peso total en los arcos de entrada (a los lugares de la trampa) que los de salida. Una fila o suma de filas con valores negativos o cero en la matriz de incidencia, contendrá un cerrojo
  • Trampas
    Lugar o conjunto de lugares en los que las marcas que contienen no pueden aumentar, debido a que las transiciones de entrada a esos lugares son también de salida, con mayor peso total en los arcos de salida (de los lugares de la trampa) que los de entrada. Una fila o suma de filas con valores positivos o cero en la matriz de incidencia, contendrá una trampa
  • Cerrojo / Trampa
    Es a la vez cerrojo y trampa. Una fila o suma de filas con todos los valores cero en la matriz de incidencia, contendrá un cerrojo / trampa
• Análisis dinámico (dependen del marcado inicial)
  Tienen las siguientes propiedades:
  • Cíclica
    Dado un estado inicial, desde cualquier estado accesible siempre se puede volver al estado inicial
  • Viva
    Dado un estado inicial, desde cualquier estado accesible nunca habrá una transición que ya no se pueda disparar más adelante
  • Limitada
    Todos los lugares tienen una cota superior finita