Una red de Petri , también conocida como red de lugar / transición (PT) , es uno de varios lenguajes de modelado matemático para la descripción de sistemas distribuidos . Es una clase de sistema dinámico de eventos discretos . Una red de Petri es un gráfico bipartito dirigido que tiene dos tipos de elementos, lugares y transiciones, representados como círculos blancos y rectángulos, respectivamente. Un lugar puede contener cualquier número de fichas, representadas como círculos negros. Una transición está habilitada si todos los lugares conectados a ella como entradas contienen al menos un token. Algunas fuentes [1] afirman que las redes de Petri fueron inventadas en agosto de 1939 por Carl Adam Petri—A la edad de 13 años— con el propósito de describir procesos químicos.
Al igual que los estándares de la industria tales como UML diagramas de actividad , de procesos de negocio del modelo y de la notación y las cadenas de procesos basados en eventos , redes de Petri ofrecen una notación gráfica para los procesos por etapas que incluyen la elección, iteración , y la ejecución concurrente . A diferencia de estos estándares, las redes de Petri tienen una definición matemática exacta de su semántica de ejecución, con una teoría matemática bien desarrollada para el análisis de procesos [ cita requerida ] .
Conceptos básicos de la red de Petri
Una red de Petri consta de lugares , transiciones y arcos . Los arcos van de un lugar a una transición o viceversa, nunca entre lugares o entre transiciones. Los lugares desde los que se extiende un arco hasta una transición se denominan lugares de entrada de la transición; los lugares a los que se extienden los arcos desde una transición se denominan lugares de salida de la transición.
Gráficamente, los lugares en una red de Petri pueden contener un número discreto de marcas llamadas tokens . Cualquier distribución de fichas sobre los lugares representará una configuración de la red denominada marca . En un sentido abstracto relacionado con un diagrama de red de Petri, una transición de una red de Petri puede dispararse si está habilitada , es decir, hay suficientes tokens en todos sus lugares de entrada; cuando se activa la transición, consume los tokens de entrada necesarios y crea tokens en sus lugares de salida. Un disparo es atómico, es decir, un solo paso no interrumpible.
A menos que se defina una política de ejecución (por ejemplo, un orden estricto de las transiciones, que describa la precedencia), la ejecución de las redes de Petri no es determinista : cuando se habilitan varias transiciones al mismo tiempo, se activarán en cualquier orden.
Dado que la activación no es determinista y pueden estar presentes múltiples tokens en cualquier lugar de la red (incluso en el mismo lugar), las redes de Petri son adecuadas para modelar el comportamiento concurrente de sistemas distribuidos.
Definición formal y terminología básica
Las redes de Petri son sistemas de transición de estado que amplían una clase de redes llamadas redes elementales. [2]
Definición 1. Una red es un triple dónde:
- y son conjuntos finitos disjuntos de lugares y transiciones , respectivamente.
- es un conjunto de arcos ( dirigidos) (o relaciones de flujo).
Definición 2. Dada una red N = ( P , T , F ), una configuración es un conjunto C de modo que C ⊆ P .
Definición 3. Una red elemental es una red de la forma EN = ( N , C ) donde:
- N = ( P , T , F ) es una red.
- C es tal que C ⊆ P es una configuración .
Definición 4. Una red de Petri es una red de la forma PN = ( N , M , W ), que extiende la red elemental de modo que:
- N = ( P , T , F ) es una red.
- M : P → Z es un conjunto de lugares múltiples , donde Z es un conjunto contable . M amplía el concepto de configuración y se describe comúnmente con referencia a los diagramas de red de Petri como una marca .
- W : F → Z es un arco múltiple , de modo que la cuenta (o peso) de cada arco es una medida de la multiplicidad del arco .
Si una red de Petri es equivalente a una red elemental, entonces Z puede ser el conjunto contable {0,1} y aquellos elementos en P que se asignan a 1 bajo M forman una configuración. De manera similar, si una red de Petri no es una red elemental, entonces el multiconjunto M puede interpretarse como que representa un conjunto de configuraciones que no son singleton. En este sentido, M extiende el concepto de configuración para redes elementales a las redes de Petri.
En el diagrama de una red de Petri (ver figura superior derecha), los lugares se representan convencionalmente con círculos, transiciones con rectángulos largos y estrechos y arcos como flechas unidireccionales que muestran conexiones de lugares a transiciones o transiciones a lugares. Si el diagrama fuera de una red elemental, entonces esos lugares en una configuración se representarían convencionalmente como círculos, donde cada círculo abarca un solo punto llamado símbolo . En el diagrama dado de una red de Petri (ver a la derecha), los círculos de lugar pueden abarcar más de una ficha para mostrar el número de veces que aparece un lugar en una configuración. La configuración de los tokens distribuidos en todo un diagrama de red de Petri se denomina marca .
En la figura superior (ver a la derecha), el lugar p 1 es un lugar de entrada de transición t ; mientras que el lugar p 2 es un lugar de salida para la misma transición. Sea PN 0 (figura superior) una red Petri con una marca configurada M 0 , y PN 1 (figura inferior) sea una red Petri con una marca configurada M 1 . La configuración de PN 0 permite la transición t mediante la propiedad de que todos los lugares de entrada tienen un número suficiente de tokens (mostrados en las figuras como puntos) "igual o mayor" que las multiplicidades en sus respectivos arcos at . Una vez y solo una vez que se habilita una transición, se activará la transición. En este ejemplo, el disparo de la transición t genera un mapa que tiene la marca configurada M 1 en la imagen de M 0 y da como resultado una red de Petri PN 1 , que se ve en la figura inferior. En el diagrama, la regla de activación para una transición se puede caracterizar restando un número de tokens de sus lugares de entrada igual a la multiplicidad de los respectivos arcos de entrada y acumulando un nuevo número de tokens en los lugares de salida igual a la multiplicidad de los respectivos arcos de salida.
Observación 1. El significado preciso de "igual o mayor" dependerá de las propiedades algebraicas precisas de la suma que se apliquen a Z en la regla de disparo, donde variaciones sutiles en las propiedades algebraicas pueden conducir a otras clases de redes de Petri; por ejemplo, redes de Petri algebraicas. [3]
La siguiente definición formal se basa libremente en ( Peterson 1981 ). Existen muchas definiciones alternativas.
Sintaxis
Un gráfico de red de Petri (llamado red de Petri por algunos, pero ver más abajo) es una tupla de 3 , dónde
- S es un conjunto finito de lugares
- T es un conjunto finito de transiciones
- S y T son inconexos , es decir, ningún objeto puede ser tanto un lugar como una transición.
- es un conjunto múltiple de arcos , es decir, asigna a cada arco una multiplicidad (o peso) de arcos enteros no negativos ; tenga en cuenta que ningún arco puede conectar dos lugares o dos transiciones.
La relación de flujo es el conjunto de arcos:. En muchos libros de texto, arcos sólo pueden tener multiplicidad 1. Estos textos definen a menudo las redes de Petri utilizando F en lugar de W . Cuando se utiliza esta convención, un gráfico de red de Petri es un bipartito multigrafo con particiones nodo S y T .
El preajuste de una transición t es el conjunto de sus lugares de entrada :; su postset es el conjunto de sus lugares de salida :. Las definiciones de pre y postconjuntos de lugares son análogas.
Una marca de una red de Petri (gráfico) es un conjunto múltiple de sus lugares, es decir, un mapeo. Decimos que la marca asigna a cada lugar un número de fichas .
Una red de Petri (llamada red de Petri marcada por algunos, ver arriba) es una tupla de 4, dónde
- es un gráfico de red de Petri;
- es la marca inicial , una marca del gráfico de red de Petri.
Semántica de ejecución
En palabras:
- disparar una transición t en una marca M consumetokens de cada uno de sus lugares de entrada s , y producetokens en cada uno de sus lugares de salida s
- una transición está habilitada (puede dispararse ) en M si hay suficientes tokens en sus lugares de entrada para que los consumos sean posibles, es decir, si y solo si.
En general, estamos interesados en lo que puede suceder cuando las transiciones pueden dispararse continuamente en un orden arbitrario.
Decimos que una marca M ' es accesible desde una marca M en un paso si; decimos que es accesible desde M si, dónde es el cierre transitivo reflexivo de; es decir, si es accesible en 0 o más pasos.
Para una red de Petri (marcada) , nos interesan los disparos que se pueden realizar a partir del marcado inicial . Su conjunto de marcas alcanzables es el conjunto
El gráfico de alcanzabilidad de N es la relación de transición restringido a sus marcas alcanzables . Es el espacio de estados de la red.
Una secuencia de disparo para una red de Petri con gráfico G y marca inicial es una secuencia de transiciones tal que . El conjunto de secuencias de disparo se denota como.
Variaciones sobre la definición
Como ya se señaló, una variación común es no permitir multiplicidades de arco y reemplazar la bolsa de arcos W con un conjunto simple, llamado relación de flujo ,. Esto no limita el poder expresivo ya que ambos pueden representarse entre sí.
Otra variación común, por ejemplo, en Desel y Juhás (2001), [4] es permitir que las capacidades se definan en los lugares. Esto se analiza en las extensiones siguientes.
Formulación en términos de vectores y matrices
Las marcas de una red de Petri pueden considerarse como vectores de enteros no negativos de longitud.
Su relación de transición se puede describir como un par de por matrices :
- , definido por
- , definido por
Entonces su diferencia
se puede utilizar para describir las marcas alcanzables en términos de multiplicación de matrices, como sigue. Para cualquier secuencia de transiciones w , escribapara el vector que mapea cada transición a su número de ocurrencias en w . Entonces nosotros tenemos
- .
Tenga en cuenta que debe requerirse que w sea una secuencia de disparo; permitir secuencias arbitrarias de transiciones generalmente producirá un conjunto más grande.
Propiedades matemáticas de las redes de Petri
Una cosa que hace que las redes de Petri sean interesantes es que proporcionan un equilibrio entre el poder de modelado y la capacidad de análisis: muchas cosas que uno quisiera saber sobre los sistemas concurrentes se pueden determinar automáticamente para las redes de Petri, aunque algunas de esas cosas son muy caras de determinar en general. caso. Se han estudiado varias subclases de redes de Petri que aún pueden modelar clases interesantes de sistemas concurrentes, mientras que estos problemas se vuelven más fáciles.
En Esparza y Nielsen (1995) se puede encontrar una descripción general de tales problemas de decisión , con resultados de decidibilidad y complejidad para las redes de Petri y algunas subclases. [5]
Accesibilidad
El problema de accesibilidad para las redes de Petri es decidir, dada una red de Petri N y una marca M , si.
Claramente, se trata de recorrer el gráfico de accesibilidad definido anteriormente, hasta que alcancemos la marca solicitada o sepamos que ya no se puede encontrar. Esto es más difícil de lo que parece al principio: el gráfico de accesibilidad es generalmente infinito y no es fácil determinar cuándo es seguro detenerse.
De hecho, se demostró que este problema era EXPSPACE- difícil [6] años antes de que se demostrara que era decidible en absoluto (Mayr, 1981). Se siguen publicando artículos sobre cómo hacerlo de manera eficiente. [7] En 2018, Czerwinski et al. mejoró el límite inferior y mostró que el problema no es ELEMENTAL . [8] En 2021, Jerome Leroux demostró que este problema no es recursivo primitivo, cerrando así la brecha de complejidad de larga data. [9]
Si bien la accesibilidad parece ser una buena herramienta para encontrar estados erróneos, para problemas prácticos, el gráfico construido generalmente tiene demasiados estados para calcular. Para aliviar este problema, la lógica temporal lineal se usa generalmente junto con el método del cuadro para demostrar que tales estados no se pueden alcanzar. La lógica temporal lineal utiliza la técnica de semidecisión para encontrar si efectivamente se puede alcanzar un estado, al encontrar un conjunto de condiciones necesarias para que se alcance el estado y luego demostrar que esas condiciones no se pueden satisfacer.
Vivacidad
Se puede describir que las redes de Petri tienen diferentes grados de vida. . Una red de Petri se llama -vive si y solo si todas sus transiciones son-vivir, donde hay una transición
- muerto , si nunca puede disparar, es decir, no está en ninguna secuencia de disparo en
- -vivo ( potencialmente disparable ), si y solo si puede disparar, es decir, está en alguna secuencia de disparo en
- -vive si puede disparar arbitrariamente a menudo, es decir, si por cada entero positivo k , ocurre al menos k veces en alguna secuencia de disparo en
- -vive si puede disparar infinitamente a menudo, es decir, si hay alguna secuencia de disparo fija (necesariamente infinita) en la que por cada entero positivo k , la transiciónocurre al menos k veces,
- -vivir (en vivo ) si siempre puede disparar, es decir, es-vivir en cada marca alcanzable en
Tenga en cuenta que estos son requisitos cada vez más estrictos: -la vida implica -vida, por .
Estas definiciones están de acuerdo con la descripción general de Murata, [10] que además utiliza-vive como un término para los muertos .
Delimitación
Un lugar en una red de Petri se denomina delimitado por k si no contiene más de k fichas en todas las marcas accesibles, incluida la marca inicial; se dice que es seguro si está acotado por 1; está acotado si está acotado por k para algún k .
Una red de Petri (marcada) se llama delimitada por k , segura o limitada cuando todos sus lugares lo son. Una red de Petri (gráfico) se denomina (estructuralmente) acotada si está acotada para cada posible marcado inicial.
Tenga en cuenta que una red de Petri está acotada si y solo si su gráfico de accesibilidad es finito.
La delimitación se puede decidir mirando la cobertura , construyendo el Karp- Miller Tree.
Puede ser útil imponer explícitamente un límite en los lugares de una red determinada. Esto se puede utilizar para modelar recursos limitados del sistema.
Algunas definiciones de redes de Petri permiten explícitamente esto como una característica sintáctica. [11] Formalmente, las redes de Petri con capacidad de lugar se pueden definir como tuplas., dónde es una red de Petri, una asignación de capacidades a (algunos o todos) lugares, y la relación de transición es la habitual restringida a las marcas en las que cada lugar con una capacidad tiene como máximo esa cantidad de fichas.
Por ejemplo, si en la red N , a ambos lugares se les asigna la capacidad 2, obtenemos una red de Petri con capacidades de lugar, digamos N2 ; su gráfico de accesibilidad se muestra a la derecha.
Alternativamente, los lugares se pueden delimitar extendiendo la red. Para ser exactos, un lugar se puede hacer delimitado por k agregando un "contra-lugar" con flujo opuesto al del lugar, y agregando tokens para hacer el total en ambos lugares k .
Redes de Petri discretas, continuas e híbridas
Así como para eventos discretos, existen redes de Petri para procesos continuos e híbridos discretos-continuos [12] que son útiles en la teoría de control discreto, continuo e híbrido , [13] y se relacionan con autómatas discretos, continuos e híbridos .
Extensiones
Hay muchas extensiones de las redes de Petri. Algunos de ellos son completamente compatibles con versiones anteriores (por ejemplo , redes de Petri de colores ) con la red de Petri original, algunos añaden propiedades que no se pueden modelar en el formalismo de la red de Petri original (por ejemplo, redes de Petri cronometradas). Aunque los modelos compatibles con versiones anteriores no amplían el poder computacional de las redes de Petri, pueden tener representaciones más concisas y pueden ser más convenientes para el modelado. [14] Las extensiones que no se pueden transformar en redes de Petri son a veces muy poderosas, pero por lo general carecen de la gama completa de herramientas matemáticas disponibles para analizar las redes de Petri ordinarias.
El término red de Petri de alto nivel se utiliza para muchos formalismos de red de Petri que amplían el formalismo básico de red P / T; esto incluye las redes de Petri de colores, las redes de Petri jerárquicas como las redes dentro de las redes y todas las demás extensiones descritas en esta sección. El término también se usa específicamente para el tipo de redes de colores compatibles con CPN Tools .
Una breve lista de posibles extensiones:
- Tipos adicionales de arcos; dos tipos comunes son:
- un arco de reinicio no impone una condición previa al disparo y vacía el lugar cuando se dispara la transición; esto hace que la accesibilidad sea indecidible, [15] mientras que algunas otras propiedades, como la terminación, siguen siendo decidibles; [dieciséis]
- un arco inhibidor impone la condición previa de que la transición solo puede dispararse cuando el lugar está vacío; esto permite que se expresen cálculos arbitrarios sobre números de tokens, lo que completa el formalismo de Turing e implica la existencia de una red universal. [17]
- En una red de Petri estándar, las fichas son indistinguibles. En una red de Petri coloreada , cada ficha tiene un valor. [18] En herramientas populares para redes de Petri coloreadas, como CPN Tools , los valores de los tokens se escriben y pueden probarse (usando expresiones de protección ) y manipularse con un lenguaje de programación funcional . Una subsidiaria de las redes de Petri de colores son las redes de Petri bien formadas , donde las expresiones de arco y guardia están restringidas para facilitar el análisis de la red.
- Otra extensión popular de las redes de Petri es la jerarquía; Esto en forma de diferentes puntos de vista que apoyan los niveles de refinamiento y abstracción fue estudiado por Fehling. Otra forma de jerarquía se encuentra en las llamadas redes de Petri de objetos o sistemas de objetos donde una red de Petri puede contener redes de Petri como sus tokens, lo que induce una jerarquía de redes de Petri anidadas que se comunican mediante la sincronización de transiciones en diferentes niveles. Ver [19] para una introducción informal a las redes de Petri de objetos.
- Un sistema de adición de vectores con estados (VASS) es un formalismo equivalente a las redes de Petri. Sin embargo, puede verse superficialmente como una generalización de las redes de Petri. Considere un autómata de estado finito donde cada transición está etiquetada por una transición de la red de Petri. La red de Petri se sincroniza luego con el autómata de estado finito, es decir, se toma una transición en el autómata al mismo tiempo que la transición correspondiente en la red de Petri. Solo es posible realizar una transición en el autómata si la correspondiente transición en la red de Petri está habilitada, y solo es posible disparar una transición en la red de Petri si hay una transición desde el estado actual en el autómata etiquetado por ella. . (La definición de VASS generalmente se formula de manera ligeramente diferente).
- Las redes de Petri priorizadas agregan prioridades a las transiciones, por lo que una transición no puede disparar, si se habilita una transición de mayor prioridad (es decir, puede disparar). Por lo tanto, las transiciones están en grupos de prioridad y, por ejemplo, el grupo de prioridad 3 solo puede disparar si todas las transiciones están deshabilitadas en los grupos 1 y 2. Dentro de un grupo de prioridad, el disparo todavía no es determinista.
- La propiedad no determinista ha sido muy valiosa, ya que permite al usuario abstraer una gran cantidad de propiedades (dependiendo de para qué se utilice la red). En ciertos casos, sin embargo, surge la necesidad de modelar también el tiempo, no solo la estructura de un modelo. Para estos casos, las redes de Petri cronometradas han evolucionado, donde hay transiciones cronometradas y posiblemente transiciones no cronometradas (si las hay, las transiciones no cronometradas tienen mayor prioridad que las cronometradas). Una subsidiaria de las redes de Petri cronometradas son las redes de Petri estocásticas que agregan tiempo no determinista a través de la aleatoriedad ajustable de las transiciones. La distribución aleatoria exponencial se usa generalmente para "cronometrar" estas redes. En este caso, el gráfico de accesibilidad de las redes se puede utilizar como una cadena de Markov en tiempo continuo (CTMC).
- Dualistic Petri Nets (dP-Nets) es una extensión de Petri Net desarrollada por E. Dawis, et al. [20] para representar mejor el proceso del mundo real. Los dP-Nets equilibran la dualidad de cambio / no cambio, acción / pasividad, (transformación) tiempo / espacio, etc., entre las construcciones bipartitas de Petri Net de transformación y lugar que dan como resultado la característica única de la marca de transformación , es decir, cuando el la transformación está "funcionando", está marcado. Esto permite que la transformación se active (o se marque) varias veces, lo que representa el comportamiento del rendimiento del proceso en el mundo real. El marcado de la transformación asume que el tiempo de transformación debe ser mayor que cero. Un tiempo de transformación cero utilizado en muchas redes de Petri típicas puede ser matemáticamente atractivo pero poco práctico para representar procesos del mundo real. dP-Nets también explota el poder de la abstracción jerárquica de Petri Nets para representar la arquitectura del proceso . Los sistemas de procesos complejos se modelan como una serie de redes más simples interconectadas a través de varios niveles de abstracción jerárquica. La arquitectura de proceso de un conmutador de paquetes se demuestra en, [21] donde los requisitos de desarrollo se organizan alrededor de la estructura del sistema diseñado.
Hay muchas más extensiones para las redes de Petri, sin embargo, es importante tener en cuenta que a medida que aumenta la complejidad de la red en términos de propiedades extendidas, más difícil es usar herramientas estándar para evaluar ciertas propiedades de la red. Por esta razón, es una buena idea utilizar el tipo de red más simple posible para una determinada tarea de modelado.
Restricciones
En lugar de extender el formalismo de la red de Petri, también podemos considerar restringirlo y observar tipos particulares de redes de Petri, obtenidos al restringir la sintaxis de una manera particular. Las redes de Petri ordinarias son las redes donde todos los pesos de arco son 1. Restringiendo aún más, los siguientes tipos de redes de Petri ordinarias se utilizan y estudian comúnmente:
- En una máquina de estado (SM), cada transición tiene un arco entrante y un arco saliente, y todas las marcas tienen exactamente una ficha. Como consecuencia, no puede no ser concurrencia , pero no puede haber conflicto (es decir, no determinismo ). Matemáticamente:
- En un gráfico marcado (MG), cada lugar tiene un arco entrante y un arco saliente. Esto significa que no pueden no ser conflicto , pero no puede haber concurrencia . Matemáticamente:
- En una red de libre elección (FC), cada arco desde un lugar a una transición es el único arco desde ese lugar o el único arco hacia esa transición, es decir, puede haber concurrencia y conflicto, pero no al mismo tiempo . Matemáticamente:
- Libre elección ampliada (EFC): una red de Petri que se puede transformar en una FC .
- En una red de elección asimétrica (AC), la concurrencia y el conflicto (en suma, confusión ) pueden ocurrir, pero no simétricamente . Matemáticamente:
Redes de flujo de trabajo
Las redes de flujo de trabajo ( redes WF) son una subclase de redes de Petri que pretenden modelar el flujo de trabajo de las actividades del proceso. [22] Las transiciones WF-net se asignan a tareas o actividades, y los lugares se asignan a las condiciones pre / post. Las redes WF tienen requisitos estructurales y operativos adicionales, principalmente la adición de un solo lugar de entrada (fuente) sin transiciones previas, y un lugar de salida (sumidero) sin las siguientes transiciones. En consecuencia, se pueden definir marcas de inicio y finalización que representen el estado del proceso.
Las redes WF tienen la propiedad de solidez , [22] que indica que un proceso con una marca de inicio de k tokens en su lugar de origen, puede alcanzar la marca de estado de terminación con k tokens en su lugar de sumidero (definido como k -sound WF-net) . Además, todas las transiciones en el proceso podrían dispararse (es decir, para cada transición hay un estado accesible en el que la transición está habilitada). Un sonido general (sonido G) WF-net se define como un sonido k para cada k > 0. [23]
Un camino dirigido en la red de Petri se define como la secuencia de nodos (lugares y transiciones) enlazados por los arcos dirigidos. Una ruta elemental incluye todos los nodos de la secuencia solo una vez.
Una red de Petri bien manejada es una red en la que no hay caminos elementales completamente distintos entre un lugar y una transición (o transición y un lugar), es decir, si hay dos caminos entre el par de nodos, estos caminos comparten un nodo. . Una red WF acíclica bien manejada es sólida (sonido G). [24]
Extended WF-net es una red de Petri que se compone de una WF-net con transición adicional t (transición de retroalimentación). El lugar del sumidero está conectado como el lugar de entrada de transición ty el lugar de la fuente como su lugar de salida. El disparo de la transición provoca la iteración del proceso (Nota: la red WF extendida no es una red WF). [22]
WRI (Bien manejado con iteración regular) WF-net, es un WF-net acíclico extendido bien manejado. WRI-WF-net se puede construir como una composición de redes, es decir, reemplazando una transición dentro de una WRI-WF-net por una subred que es una WRI-WF-net. El resultado también es WRI-WF-net. Las redes WRI-WF son de sonido G, [24] por lo tanto, utilizando solo bloques de construcción de la red WRI-WF, se pueden obtener redes WF que son de sonido G por construcción.
La matriz de estructura de diseño (DSM) puede modelar relaciones de proceso y utilizarse para la planificación de procesos. Las redes DSM son la realización de planes basados en DSM en procesos de flujo de trabajo mediante redes de Petri y son equivalentes a las redes WRI-WF. El proceso de construcción de la red DSM asegura la propiedad de solidez de la red resultante.
Otros modelos de concurrencia
Se han propuesto otras formas de modelar la computación concurrente, incluidos los sistemas de adición de vectores , las máquinas comunicantes de estados finitos , las redes de procesos de Kahn , el álgebra de procesos , el modelo de actor y la teoría de trazas . [25] Los diferentes modelos ofrecen compensaciones de conceptos como composicionalidad , modularidad y localidad.
En el capítulo de Winskel y Nielsen se propone un enfoque para relacionar algunos de estos modelos de concurrencia. [26]
Áreas de aplicación
- Cálculo diferencial booleano [27]
- Modelado de procesos comerciales [28] [29]
- Biología Computacional [30] [31]
- Programación concurrente [32]
- Ingeniería de control [13] [33] [34]
- Análisis de datos [35]
- Diagnóstico (inteligencia artificial) [36]
- Control de proceso discreto [37] [38] [39]
- Teoría de juegos [40]
- Redes de proceso Kahn [41]
- Modelado de procesos [42] [43] [44]
- Ingeniería de confiabilidad [ cita requerida ]
- Simulación [28]
- Diseño de software [12]
- Sistemas de gestión del flujo de trabajo [45] [43] [44]
Ver también
- Máquina de estados finitos
- Lenguaje de marcado de Petri Net
- Petriscript
- Arquitectura de proceso
- Sistemas de adición de vectores
Referencias
- ^ Petri, Carl Adam; Reisig, Wolfgang (2008). "Red de Petri" . Scholarpedia . 3 (4): 6477. Código bibliográfico : 2008SchpJ ... 3.6477P . doi : 10.4249 / scholarpedia.6477 .
- ^ Rozenburg, G .; Engelfriet, J. (1998). "Sistemas de redes elementales". En Reisig, W .; Rozenberg, G. (eds.). Conferencias sobre redes de Petri I: Modelos básicos - Avances en redes de Petri . Apuntes de conferencias en informática. 1491 . Saltador. págs. 12-121.
- ^ Reisig, Wolfgang (1991). "Redes de Petri y especificaciones algebraicas". Informática Teórica . 80 (1): 1–34. doi : 10.1016 / 0304-3975 (91) 90203-e .
- ^ Desel, Jörg; Juhás, Gabriel (2001). "¿Qué es una red de Petri? Respuestas informales para el lector informado". En Ehrig, Hartmut ; et al. (eds.). Unificando las redes de Petri . LNCS. 2128 . Saltador. págs. 1–25. doi : 10.1007 / 3-540-45541-8_1 . ISBN 9783540430674.
- ^ Esparza, Javier; Nielsen, Mogens (1995) [1994]. "Problemas de decidibilidad para las redes de Petri - una encuesta" . Boletín de la EATCS (Ed. Revisada) . Consultado el 14 de mayo de 2014 .
- ^ Lipton, R. (1976). "El problema de la accesibilidad requiere espacio exponencial" . Informe técnico 62 .
- ^ Küngas, P. (26 al 29 de julio de 2005). La comprobación de la accesibilidad de la red de Petri es polinomial con jerarquías de abstracción óptimas . Actas del 6º Simposio Internacional sobre Abstracción, Reformulación y Aproximación — SARA 2005. Airth Castle, Escocia, Reino Unido. Archivado desde el original el 9 de febrero de 2012 . Consultado el 10 de julio de 2008 .
- ^ Czerwinski, Wojciech; Lasota, Slawomir; Lazic, Ranko; Leroux, Jerome; Mazowiecki, Filip (2018). "El problema de accesibilidad para las redes de Petri no es elemental (Resumen extendido)". arXiv : 1809.07115 [ cs.FL ].
- ^ Leroux, Jérôme (2021). "El problema de accesibilidad para las redes de Petri no es recursivo primitivo". arXiv : 2104.12695 [ cs.LO ].
- ^ Murata, Tadao (abril de 1989). "Redes de Petri: Propiedades, Análisis y Aplicaciones" . Actas del IEEE . 77 (4): 541–558. doi : 10.1109 / 5.24143 . Consultado el 13 de octubre de 2014 .
- ^ "Redes de Petri" . www.techfak.uni-bielefeld.de .
- ^ a b Kučera, Erik; Haffner, Oto; Drahoš, Peter; Cigánek, Ján; Leskovský, Roman; Štefanovič, Juraj (enero de 2020). "Nueva herramienta de software para el modelado y control de sistemas híbridos y de eventos discretos utilizando redes de Petri interpretadas cronometradas" . Ciencias Aplicadas . 10 (15): 5027. doi : 10.3390 / app10155027 .
- ^ a b David, René; Alla, Hassane (2005). Redes de Petri discretas, continuas e híbridas . Saltador. ISBN 978-3-540-22480-8.
- ^ Jensen, Kurt (1997). "Una breve introducción a las redes de Petri de colores" (PDF) . Una breve introducción a las redes de Petri de colores . Apuntes de conferencias en informática. 1217 . págs. 203–208. doi : 10.1007 / BFb0035389 . ISBN 978-3-540-62790-6.
- ^ Araki, T .; Kasami, T. (1977). "Algunos problemas de decisión relacionados con el problema de accesibilidad de las redes de Petri". Informática Teórica . 3 (1): 85-104. doi : 10.1016 / 0304-3975 (76) 90067-0 .
- ^ Dufourd, C .; Finkel, A .; Schnoebelen, Ph. (1998). "Restablecer redes entre decidabilidad e indecidibilidad". Actas del 25º Coloquio Internacional sobre Autómatas, Lenguajes y Programación . LNCS . 1443 . págs. 103-115.
- ^ Zaitsev, DA (2013). "Hacia la Red de Petri Universal Mínima". Transacciones IEEE sobre sistemas, hombre y cibernética: sistemas . 44 : 47–58. doi : 10.1109 / TSMC.2012.2237549 . S2CID 6561556 .
- ^ "Introducción muy breve a CP-nets" . Departamento de Ciencias de la Computación, Universidad de Aarhus, Dinamarca.
- ^ "LLPN - Redes de Petri de lógica lineal" . Archivado desde el original el 3 de noviembre de 2005 . Consultado el 6 de enero de 2006 .
- ^ Dawis, EP; Dawis, JF; Koo, Wei-Pin (2001). Arquitectura de sistemas informáticos que utilizan redes de Petri dualistas . 2001 Conferencia Internacional IEEE sobre Sistemas, Hombre y Cibernética. 3 . págs. 1554-1558.
- ^ Dawis, EP (2001). Arquitectura de una pila de protocolos SS7 en una plataforma de conmutación de banda ancha utilizando redes de Petri dualistas . 2001 Conferencia IEEE Pacific Rim sobre comunicaciones, computadoras y procesamiento de señales. 1 . págs. 323–326.
- ^ a b c van der Aalst, WMP (1998). "La aplicación de las redes de Petri a la gestión del flujo de trabajo" (PDF) . Revista de circuitos, sistemas y computadoras . 8 (1): 21–66. CiteSeerX 10.1.1.30.3125 . doi : 10.1142 / s0218126698000043 .
- ^ van Hee, K .; Sidorova, N .; Voorhoeve, M. (2003). "Solidez y separabilidad de las redes de flujo de trabajo en el enfoque de refinamiento paso a paso" (PDF) . En van der Aalst, WMP; Lo mejor, E. (eds.). Aplicación y teoría de las redes de Petri 2003 . Lect Notes in Comput Sci. 2678 . Saltador. págs. 337–356.
- ^ a b Ping, L .; Hao, H .; Jian, L. (2004). Moldt, Daniel (ed.). Sobre la solidez y solidez de las redes de flujo de trabajo . Proc del III Taller de Modelado de Objetos, Componentes y Agentes. 571 . Aarhus, Dinamarca: DAIMI PB. págs. 21–36.
- ^ Mazurkiewicz, Antoni (1995). "Introducción a la teoría de la traza". En Diekert, V .; Rozenberg, G. (eds.). El libro de las huellas . Singapur: World Scientific. págs. 3-67.
- ^ Winskel, G .; Nielsen, M. "Modelos de concurrencia" (PDF) . Manual de lógica y fundamentos de la informática . 4 . OUP. págs. 1-148. Archivado desde el original (PDF) el 4 de mayo de 2020.
- ^ Scheuring, Rainer; Wehlan, Herbert "Hans" (1 de diciembre de 1991) [julio de 1991]. Bretthauer, Georg (ed.). "Der Boolesche Differentialkalkül - eine Methode zur Analyze und Synthese von Petri-Netzen" [El cálculo diferencial booleano - Un método para el análisis y síntesis de redes de Petri]. En - Automatisierungstechnik - Methoden und Anwendungen der Steuerungs-, Regelungs- und Informationstechnik (en alemán). Stuttgart, Alemania: R. Oldenbourg Verlag . Consultado el 16 de octubre de 2017 . (8 páginas) . 39 (7): 226–233. doi : 10.1524 / auto.1991.39.112.226 . ISSN 0178-2312 . S2CID 56766796 . Archivado desde el original el 16 de octubre de 2017
- ^ a b van der Aalst, WMP; Stahl, C. Procesos de negocio de modelado: un enfoque orientado a la red de Petri . MIT Press. págs. 1-400.
- ^ van der Aalst, WMP (2018). "Gestión de Procesos de Negocio". Enciclopedia de sistemas de bases de datos, segunda edición . Saltador. págs. 370–374. doi : 10.1007 / 978-1-4614-8265-9_1179 . ISBN 978-1-4614-8266-6.
- ^ Favrin, Bean (2 de septiembre de 2014). "esyN: creación de redes, compartir y publicar" . PLOS ONE . 9 (9): e106035. Código bibliográfico : 2014PLoSO ... 9j6035B . doi : 10.1371 / journal.pone.0106035 . PMC 4152123 . PMID 25181461 .
- ^ Koch, Ina; Reisig, Wolfgang; Schreiber, Falk (2011). Modelado en biología de sistemas: el enfoque de la red de Petri . Biología Computacional. 16 . Saltador. doi : 10.1007 / 978-1-84996-474-6 . ISBN 978-1-84996-473-9.
- ^ Kristensen, LM; Westergaard, M. (2010). Generación automática de código basado en estructura a partir de redes de Petri coloreadas: una prueba de concepto . Métodos formales para sistemas críticos industriales - XV Taller Internacional, FMICS 2010. Apuntes de conferencias en Ciencias de la Computación. 6371 . págs. 215-230. doi : 10.1007 / 978-3-642-15898-8_14 .
- ^ Gao, X .; Hu, Xinyan (2020). "Un control robusto de la red neuronal de Petri Net para el nuevo modelo de proceso de relleno de pasta" . Acceso IEEE . 8 : 18420–18425. doi : 10.1109 / ACCESS.2020.2968510 . S2CID 210994447 .
- ^ Kučera, Erik; Haffner, Oto; Drahoš, Peter; Leskovský, Roman; Cigánek, Ján (enero de 2020). "PetriNet Editor + PetriNet Engine: nueva herramienta de software para el modelado y control de sistemas de eventos discretos utilizando redes de Petri y generación de código" . Ciencias Aplicadas . 10 (21): 7662. doi : 10.3390 / app10217662 .
- ^ van der Aalst, WMP (2016). Minería de procesos: ciencia de datos en acción, segunda edición . Saltador. doi : 10.1007 / 978-3-662-49851-4 . ISBN 978-3-662-49850-7. S2CID 12806779 .
- ^ Carmona, J .; van Dongen, BF; Solti, A .; Weidlich, M. (2018). Verificación de conformidad: procesos y modelos relacionados . Saltador. doi : 10.1007 / 978-3-319-99414-7 . ISBN 978-3-319-99413-0. S2CID 53250018 .
- ^ Fernández, JL; Sanz, R .; Paz, E .; Alonso, C. (19 a 23 de mayo de 2008). "Uso de redes de Petri binarias jerárquicas para construir aplicaciones robustas de robots móviles: RoboGraph". Conferencia Internacional IEEE sobre Robótica y Automatización, 2008 . Pasadena, CA, Estados Unidos. págs. 1372-1377. doi : 10.1109 / ROBOT.2008.4543394 .
- ^ Mendes, J. Marco; Leitão, Paulo; Colombo, Armando W .; Restivo, Francisco (2012). "Redes de Petri de alto nivel para la descripción y control de procesos en sistemas de fabricación orientados a servicios" . Revista Internacional de Investigación en Producción . Taylor y Francis. 50 (6): 1650–1665. doi : 10.1080 / 00207543.2011.575892 . S2CID 39688855 .
- ^ Fahland, D .; Gierds, C. (2013). Análisis y finalización de diseños de middleware para la integración empresarial mediante redes de Petri de colores . Ingeniería de Sistemas de Información Avanzada - 25th International Conference, CAiSE 2013. Lecture Notes in Computer Science. 7908 . págs. 400–416. doi : 10.1007 / 978-3-642-38709-8_26 .
- ^ Clempner, Julio (2006). "Modelado de juegos de ruta más corta con redes de Petri: una teoría basada en Lyapunov" . Revista Internacional de Matemática Aplicada e Informática . 16 (3): 387–397. ISSN 1641-876X .
- ^ Bernardeschi, C .; De Francesco, N .; Vaglini, G. (1995). "Semántica de redes de Petri para redes de flujo de datos" . Acta Informatica . 32 (4): 347–374. doi : 10.1007 / BF01178383 . S2CID 7285573 .
- ^ van der Aalst, diputado Wil; Stahl, Christian; Westergaard, Michael (2013). "Estrategias para el modelado de procesos complejos utilizando redes de Petri de colores" . Trans. Petri Nets Otro modelo. Concurrir . Apuntes de conferencias en informática. 7 : 6-55. doi : 10.1007 / 978-3-642-38143-0_2 . ISBN 978-3-642-38142-3.
- ^ a b van der Aalst, WMP (2018). "Patrones de flujo de trabajo". Enciclopedia de sistemas de bases de datos, segunda edición . Saltador. págs. 4717–4718. doi : 10.1007 / 978-1-4614-8265-9_826 . ISBN 978-1-4614-8266-6.
- ^ a b van der Aalst, WMP (2018). "Análisis del modelo de flujo de trabajo". Enciclopedia de sistemas de bases de datos, segunda edición . Saltador. págs. 4716–4717. doi : 10.1007 / 978-1-4614-8265-9_1476 . ISBN 978-1-4614-8266-6.
- ^ ter Hofstede, Arthur HM; van der Aalst, diputado Wil; Adams, Michael; Russell, Nick (2010). Hofstede, Arthur H. M; Aalst, Wil M. P; Adams, Michael; Russell, Nick (eds.). Automatización de procesos empresariales modernos: YAWL y su entorno de soporte . doi : 10.1007 / 978-3-642-03121-2 . ISBN 978-3-642-03122-9.
Otras lecturas
- Cardoso, Janette; Camargo, Heloisa (1999). Borrosidad en las redes de Petri . Physica-Verlag. ISBN 978-3-7908-1158-2.
- Chiachio, Manuel; Chiachio, Juan; Presscott, Darren; Andrews, John (2018). "Un nuevo paradigma para la representación del conocimiento incierto mediante 'redes de Petri plausibles ' " . Ciencias de la información . 453 (julio de 2018): 323-345. doi : 10.1016 / j.ins.2018.04.029 .
- Grobelna, Iwona (2011). "Verificación formal de la especificación del controlador lógico embebido con deducción informática en lógica temporal". Przeglad Elektrotechniczny . 87 (12a): 47–50.
- Jensen, Kurt (1997). Redes de Petri de colores . Springer Verlag. ISBN 978-3-540-62867-5.
- Pataricza, András (2004). Formális módszerek az informatikában (Métodos formales en informática) . TYPOTEX Kiadó. ISBN 978-963-9548-08-4.
- Peterson, James Lyle (1977). "Redes de Petri". Encuestas de computación ACM . 9 (3): 223–252. doi : 10.1145 / 356698.356702 . hdl : 10338.dmlcz / 135597 . S2CID 3605804 .
- Peterson, James Lyle (1981). Teoría de la red de Petri y modelado de sistemas . Prentice Hall. ISBN 978-0-13-661983-3.
- Petri, Carl Adam (1962). Kommunikation mit Automaten (tesis doctoral). Universidad de Bonn.
- Petri, Carl Adam; Reisig, Wolfgang (2008). "Red de Petri" . Scholarpedia . 3 (4): 6477. Código bibliográfico : 2008SchpJ ... 3.6477P . doi : 10.4249 / scholarpedia.6477 .
- Reisig, Wolfgang (1992). Una introducción al diseño de redes de Petri . Springer-Verlag. ISBN 978-3-540-52044-3.
- Riemann, Robert-Christoph (1999). Modelado de sistemas concurrentes: métodos estructurales y semánticos en el cálculo de redes de Petri de alto nivel . Herbert Utz Verlag. ISBN 978-3-89675-629-9.
- Störrle, Harald (2000). Modelos de Arquitectura de Software - Diseño y Análisis con UML y Petri-Nets . Libros a pedido. ISBN 978-3-8311-1330-9.
- Zaitsev, Dmitry (2013). Clanes de Redes de Petri: Verificación de protocolos y evaluación de desempeño de redes . Editorial Académica LAP LAMBERT. ISBN 978-3-659-42228-7.
- Zhou, Mengchu ; Dicesare, Frank (1993). Síntesis de Petri Net para el control de eventos discretos de sistemas de fabricación . Editores académicos de Kluwer. ISBN 978-0-7923-9289-7.
- Zhou, Mengchu ; Venkatesh, Kurapati (1998). Modelado, simulación y control de sistemas de fabricación flexibles: un enfoque de red de Petri . Publicaciones científicas mundiales. ISBN 978-981-02-3029-6.
enlaces externos
- Mundo de las redes de Petri
- Lenguaje de marcado de Petri Net
- Implementación Java de redes de Petri en la biblioteca jBPT (ver módulo jbpt-petri)
- Simulador de red Java Petri
- Introducción al tutorial basado en Flash de Petia Wohed a la tecnología de flujo de trabajo con redes de Petri
- Lista de herramientas de red de Petri