Red de Petri algebraica
La red de Petri algebraica ( inglés algebraic Petri net, APN ) es una extensión de las redes de Petri convencionales , en las que los marcadores ordinarios se reemplazan por elementos de tipos de datos algebraicos [1] . Este formalismo es en muchos aspectos similar a las redes de Petri coloreadas [2] , sin embargo, en el caso de las redes algebraicas, la semántica de los tipos de datos viene dada por un sistema de axiomas que permite realizar pruebas y cálculos sobre los tipos que lo utilizan.
Introducido por primera vez por Jacques Waterren en 1985 [3] , mejorado por Wolfgang Reisig [4] .
El formalismo incluye dos componentes:
- la parte de control dada por la red de Petri;
- un dato especificado por uno o más tipos de datos algebraicos.
Los tipos de datos algebraicos se pueden dividir en dos partes:
- una firma que define constantes y operaciones válidas en el álgebra de términos .
- axiomatización que define la semántica de las operaciones definidas por la firma.
La parte de control incluye:
- posiciones que contienen conjuntos múltiples de marcadores; los marcadores son elementos de un álgebra de términos construidos usando una firma, cada posición contiene uno y solo un conjunto múltiple de términos, la posición está tipificada por el conjunto múltiple asignado a ella;
- los arcos se pueden etiquetar mediante múltiples conjuntos de términos definidos o libres, al igual que para las posiciones, los términos se definen a partir de tipos algebraicos de la firma;
- las transiciones son eventos que se disparan cada vez que hay suficientes marcadores en las posiciones de entrada para mover el marcador a lo largo de cada uno de los arcos de entrada y, al mismo tiempo, se cumple la condición de activación (protección) de la transición.
En el momento en que se dispara el evento, los marcadores producidos se mueven a las posiciones de destino de los arcos de salida. Para determinar la semántica de las operaciones, verifique si se cumplen las condiciones especificadas y calcule los términos de salida, por regla general, se utilizan técnicas de reescritura de términos [5] .
Las redes algebraicas de Petri sirvieron como base para el desarrollo de variantes más complejas del mismo formalismo, en particular CO-OPN ( Concurrent Object-Oriented Petri Nets ).
Ejemplo
Un ejemplo de una red de Petri algebraica diseñada para modelar el problema de los filósofos comedores :
Se utilizan dos tipos de datos algebraicos. Uno de ellos ( Fork) define el álgebra de bifurcaciones, el otro ( ) define el Philosopherálgebra de los filósofos. Dado que todos los filósofos pueden tomar la bifurcación izquierda sin tomar la derecha, ejecutar este modelo puede conducir a un punto muerto . Al comienzo del modelo, solo es posible la transición goEat. goEatSi se ha activado al menos uno , las transiciones takeLy también se permiten takeR.
Notas
- ↑ Ehrig, Hartmut. Fundamentos de Especificación Algebraica 1 : Ecuaciones y Semántica Inicial . - Berlín: Springer Berlin Heidelberg, 1985. - 321 p. - ISBN 978-3-642-69962-7 , 3-642-69962-6, 978-3-642-69964-1, 3-642-69964-2. Archivado el 4 de septiembre de 2020 en Wayback Machine .
- ↑ Jensen K. Redes de Petri coloreadas - Berlín: Springer-Verlag, 1997. - 236 p.
- ↑ Vautherin J. Especificaciones de sistemas paralelos con Coloured Petrinets y especificaciones algebraicas. Taller Europeo sobre Aplicaciones y Teoría de las Redes de Petri - Berlín, NY: Springer-Verlag, 1987. - P. 293-308.
- ↑ Reisig W. Redes de Petri y especificaciones algebraicas // Teor. computar ciencia - 1991. - vol. 80. - N° 1. - Pág. 1-34.
- ↑ Dick AJ, Watson P. Reescritura de términos ordenados por orden // Comput. J. - 1991. - vol. 34. - N° 1. - Pág. 16-19.