Red de Petri

La red de Petri  es un objeto matemático utilizado para modelar sistemas discretos dinámicos, propuesto por Carl Petri en 1962 .

Se define como un multigrafo orientado bipartito , que consta de dos tipos de vértices: posiciones y transiciones, conectados por arcos. Los vértices del mismo tipo no se pueden conectar directamente. Las posiciones pueden contener etiquetas (marcadores) que pueden moverse por la red. Un evento es la activación de una transición, en la que las etiquetas de las posiciones de entrada de esta transición se mueven a las posiciones de salida. Los eventos ocurren instantáneamente o en diferentes momentos, bajo ciertas condiciones.

La red de Petri es un multigrafo, ya que permite la existencia de múltiples arcos de un vértice del grafo a otro. Dado que los arcos son dirigidos, este es un multigrafo dirigido. Los vértices del grafo se pueden dividir en dos conjuntos (posiciones y transiciones) de tal manera que cada arco estará dirigido desde un elemento de un conjunto (posiciones o transiciones) a un elemento de otro conjunto (transiciones o posiciones); por lo tanto, tal gráfico es un multigrafo dirigido bipartito.

Inicialmente desarrollado para modelar sistemas con componentes paralelos que interactúan; Petri formuló las principales disposiciones de la teoría de la comunicación de los componentes asíncronos de un sistema informático en su tesis doctoral "Comunicación de autómatas" [1] .

Dinámica

El proceso de funcionamiento de la red de Petri se puede representar visualmente mediante un gráfico de marcas alcanzables. El estado de la red está determinado únicamente por su marcado: la distribución de chips por posición. Los vértices del gráfico son marcas admisibles de la red de Petri, los arcos están marcados con el símbolo de transición disparada. Se construye un arco para cada transición excitada. La construcción se detiene cuando obtenemos marcas en las que no se excita ninguna transición, o marcas contenidas en el gráfico. Tenga en cuenta que el gráfico de marcas alcanzables es un autómata.

Tipos de redes de Petri

Algunos tipos de redes de Petri:

Análisis de redes de Petri

Las principales propiedades de una red de Petri son:

El estudio de estas propiedades se basa en el análisis de accesibilidad. Los métodos para analizar las propiedades de las redes de Petri se basan en el uso de gráficos de marcas alcanzables (de cobertura), la resolución de la ecuación de estados de la red y el cálculo de invariantes lineales de posiciones y transiciones. También se utilizan métodos de reducción auxiliar para reducir el tamaño de la red de Petri manteniendo sus propiedades, y descomposición [2] , dividiendo la red original en subredes.

Red Petri Universal

En 1974, Tilak Ajerwala demostró que la red de Petri inhibidora es un sistema algorítmico universal. En la monografía de Kotov , se da un bosquejo de la prueba, que indica las reglas para codificar el programa del contador autómata de Minsky por una red inhibidora . Peterson da ejemplos de otras clases extendidas de redes de Petri que son un sistema algorítmico universal: síncronas y prioritarias. La red de Petri universal explícitamente construida [3] tenía varios miles de vértices y recientemente se redujo a 56 vértices [4] .

Redes de Petri Infinitas

Las redes de Petri infinitas se introdujeron para verificar las redes computacionales y hacer posible determinar las propiedades de las redes de Petri para estructuras regulares (lineales, arbóreas, cuadradas, triangulares, hexagonales e hipercubo [5] ) de tamaño arbitrario, obtenidas mediante la composición de fragmentos típicos.

Véase también

Notas

  1. ↑ Peterson, 1984 , pág. 11 "1.3. El origen de la teoría de las redes de Petri.
  2. ↑ Zaitsev D. A. Copia archivada del 1 de abril de 2022 en Wayback Machine Análisis compositivo de redes de Petri // Cibernética y análisis de sistemas. - 2006, N° 1. - S. 143-154.
  3. ↑ Zaitsev D. A. Copia de archivo fechada el 1 de abril de 2022 en Wayback Machine Universal Petri Net, Cybernetics and System Analysis, n.° 4, 2012, p. 24-39.
  4. ↑ Zaitsev DA Archivado el 1 de abril de 2022 en Wayback Machine Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1-12.
  5. ↑ Zaitsev D. A. Copia archivada del 1 de abril de 2022 en Wayback Machine , Shmeleva T. R. Verificación de estructuras de comunicación de hipercubo mediante redes paramétricas de Petri, cibernética y análisis de sistemas, n.º 1, 2010, págs. 119-128.

Literatura

Enlaces