Red de Petri

Una red de Petri , también conocida como red de lugar/transición ( red 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 grafo bipartito dirigido que tiene dos tipos de elementos: lugares y transiciones. Los elementos de lugar se representan como círculos blancos y los elementos de transición se representan como rectángulos. Un lugar puede contener cualquier número de tokens, representados 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, como los diagramas de actividad UML , el modelo y la notación de procesos de negocios y las cadenas de procesos impulsadas por eventos , las redes de Petri ofrecen una notación gráfica para procesos escalonados que incluyen elección, iteración y 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 ]} .

El científico informático alemán Carl Adam Petri , que dio nombre a estas estructuras, analizó las redes de Petri en profundidad en su tesis de 1962 Kommunikation mit Automaten .

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 un arco va a una transición se denominan lugares de entrada de la transición; los lugares a los que van 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 tokens sobre los lugares representará una configuración de la red llamada marcado . 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 la transición se dispara, consume los tokens de entrada requeridos 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 transiciones que describa la precedencia), la ejecución de redes de Petri no es determinista : cuando se habilitan múltiples transiciones al mismo tiempo, se activarán en cualquier orden.

Dado que el disparo no es determinista y pueden estar presentes múltiples tokens en cualquier parte de la red (incluso en el mismo lugar), las redes de Petri son adecuadas para modelar el comportamiento concurrente de sistemas distribuidos.

Las redes de Petri son sistemas de transición de estados que extienden una clase de redes llamadas redes elementales. ^[2]

Definición 1. Una red es una tupla donde${\displaystyle N=(P,T,F)}$

1. P y T son conjuntos finitos disjuntos de lugares y transiciones , respectivamente.
2. ${\displaystyle F\subseteq (P\veces T)\cup (T\veces P)}$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 tal que C ⊆ P .

Definición 3. Una red elemental es una red de la forma EN = ( N , C ) donde

1. N = ( P , T , F ) es una red.
2. 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

1. N = ( P , T , F ) es una red.
2. M : P → Z es un multiconjunto de lugar , donde Z es un conjunto contable . M extiende el concepto de configuración y se describe comúnmente con referencia a los diagramas de redes de Petri como una marca .
3. W : F → Z es un multiconjunto de arcos , de modo que el recuento (o peso) de cada arco es una medida de la multiplicidad de arcos .

Si una red de Petri es equivalente a una red elemental, entonces Z puede ser el conjunto numerable {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 la representación de un conjunto no singleton de configuraciones. 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, las transiciones con rectángulos largos y estrechos y los arcos como flechas unidireccionales que muestran conexiones de lugares con transiciones o transiciones con 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 único punto llamado token . En el diagrama dado de una red de Petri (ver a la derecha), los círculos de lugar pueden abarcar más de un token para mostrar el número de veces que aparece un lugar en una configuración. La configuración de tokens distribuidos en un diagrama de red de Petri completo se llama marcado .

En la figura superior (ver a la derecha), el lugar p ₁ es un lugar de entrada de la transición t ; mientras que, el lugar p ₂ es un lugar de salida para la misma transición. Sea PN ₀ (figura superior) una red de Petri con una marca configurada M ₀ , y PN ₁ (figura inferior) una red de Petri con una marca configurada M ₁ . La configuración de PN ₀ habilita la transición t a través de la propiedad de que todos los lugares de entrada tienen una cantidad suficiente de tokens (mostrados en las figuras como puntos) "igual o mayor" que las multiplicidades en sus respectivos arcos para t . Una vez y solo una vez que se habilita una transición, la transición se activará. En este ejemplo, el disparo de la transición t genera un mapa que tiene la marca configurada M ₁ en la imagen de M ₀ y da como resultado la red de Petri PN ₁ , que se ve en la figura inferior. En el diagrama, la regla de disparo para una transición se puede caracterizar restando una cantidad de tokens de sus lugares de entrada igual a la multiplicidad de los respectivos arcos de entrada y acumulando una nueva cantidad 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 adición que se apliquen a Z en la regla de activación, 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.

Un gráfico de red de Petri (llamado red de Petri por algunos, pero vea más abajo) es una tupla de 3 , donde${\displaystyle (S,T,W)}$

• S es un conjunto finito de lugares
• T es un conjunto finito de transiciones
• S y T son disjuntos , es decir, ningún objeto puede ser a la vez un lugar y una transición.
• ${\displaystyle W:(S\times T)\cup (T\times S)\to \mathbb {N} }$es un multiconjunto de arcos , es decir, asigna a cada arco una multiplicidad de arco (o peso) entera no negativa; 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, los arcos solo pueden tener multiplicidad 1. Estos textos a menudo definen redes de Petri utilizando F en lugar de W . Cuando se utiliza esta convención, un gráfico de red de Petri es un gráfico dirigido bipartito con particiones de nodos S y T .${\displaystyle F=\{(x,y)\mid W(x,y)>0\}}$ ${\displaystyle (S\cup T,F)}$

El preset 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 presets y postsets de lugares son análogas.${\displaystyle {}^{\bullet }t=\{s\in S\mid W(s,t)>0\}}$${\displaystyle t^{\bullet }=\{s\in S\mid W(t,s)>0\}}$

El marcado de una red de Petri (grafo) es un multiconjunto de sus lugares, es decir, una aplicación . Decimos que el marcado asigna a cada lugar un número de tokens .${\displaystyle M:S\to \mathbb {N} }$

Una red de Petri (llamada red de Petri marcada por algunos, ver arriba) es una tupla de 4 , donde${\displaystyle (S,T,W,M_{0})}$

• ${\displaystyle (S,T,W)}$es un gráfico de red de Petri;
• ${\displaystyle M_{0}}$es la marca inicial , una marca del gráfico de la red de Petri.

En palabras

• Al disparar una transición t en un marcado M se consumen tokens de cada uno de sus lugares de entrada s y se producen tokens en cada uno de sus lugares de salida s${\displaystyle W(s,t)}$${\displaystyle W(t,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 .${\displaystyle \forall s:M(s)\geq W(s,t)}$

En general, nos interesa saber qué puede ocurrir cuando las transiciones se activan continuamente en un orden arbitrario.

Decimos que una marca M' es alcanzable desde una marca M en un paso si ; decimos que es alcanzable desde M si , donde es la clausura transitiva reflexiva de ; es decir, si es alcanzable en 0 o más pasos.${\displaystyle M{\underset {G}{\longrightarrow }}M'}$${\displaystyle M{\overset {*}{\underset {G}{\longrightarrow }}}M'}$${\displaystyle {\overset {*}{\underset {G}{\longrightarrow }}}}$${\displaystyle {\underset {G}{\longrightarrow }}}$

Para una red de Petri (marcada) , nos interesan los disparos que se pueden realizar a partir del marcado inicial . Su conjunto de marcados alcanzables es el conjunto${\displaystyle N=(S,T,W,M_{0})}$${\displaystyle M_{0}}$${\displaystyle R(N)\ {\stackrel {D}{=}}\ \left\{M'{\Bigg |}M_{0}{\xrightarrow[{(S,T,W)}]{*}}M'\right\}}$

El gráfico de alcanzabilidad de N es la relación de transición restringida a sus marcas alcanzables . Es el espacio de estados de la red.${\displaystyle {\underset {G}{\longrightarrow }}}$${\displaystyle R(N)}$

Una secuencia de disparos para una red de Petri con grafo G y marcaje inicial es una secuencia de transiciones tal que . El conjunto de secuencias de disparos se denota como .${\displaystyle M_{0}}$${\displaystyle {\vec {\sigma }}=\langle t_{1}\cdots t_{n}\rangle }$${\displaystyle M_{0}{\underset {G,t_{1}}{\longrightarrow }}M_{1}\wedge \cdots \wedge M_{n-1}{\underset {G,t_{n}}{\longrightarrow }}M_{n}}$${\displaystyle L(N)}$

Una variación común es rechazar las multiplicidades de arcos 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í.${\displaystyle F\subseteq (S\times T)\cup (T\times S)}$

Otra variación común, por ejemplo, en Desel y Juhás (2001), ^[4] es permitir que las capacidades se definan en lugares. Esto se analiza en las extensiones más adelante.

Las marcas de una red de Petri pueden considerarse como vectores de números enteros no negativos de longitud .${\displaystyle (S,T,W,M_{0})}$${\displaystyle |S|}$

Su relación de transición se puede describir como un par de matrices :${\displaystyle |S|}$${\displaystyle |T|}$

• ${\displaystyle W^{-}}$, definido por${\displaystyle \forall s,t:W^{-}[s,t]=W(s,t)}$
• ${\displaystyle W^{+}}$, definido por${\displaystyle \forall s,t:W^{+}[s,t]=W(t,s).}$

Entonces su diferencia

• ${\displaystyle W^{T}=-W^{-}+W^{+}}$

se puede utilizar para describir las marcas alcanzables en términos de multiplicación de matrices, de la siguiente manera. Para cualquier secuencia de transiciones w , escriba para el vector que asigna cada transición a su número de ocurrencias en w . Entonces, tenemos${\displaystyle o(w)}$

• ${\displaystyle R(N)=\{M\mid \exists w:\ w{\text{ is a firing sequence of }}N\ {\text{ and }}\ M=M_{0}+W^{T}\cdot o(w)\}}$.

Se debe exigir que w sea una secuencia de disparo; permitir secuencias arbitrarias de transiciones generalmente producirá un conjunto más grande.

$${\displaystyle W^{-}={\begin{bmatrix}*&t1&t2\\p1&1&0\\p2&0&1\\p3&0&1\\p4&0&0\end{bmatrix}},\ W^{+}={\begin{bmatrix}*&t1&t2\\p1&0&1\\p2&1&0\\p3&1&0\\p4&0&1\end{bmatrix}},\ W^{T}={\begin{bmatrix}*&t1&t2\\p1&-1&1\\p2&1&-1\\p3&1&-1\\p4&0&1\end{bmatrix}}}$$

$${\displaystyle M_{0}={\begin{bmatrix}1&0&2&1\end{bmatrix}}}$$

This section needs expansion. You can help by adding to it. (September 2022)

Meseguer y Montanari consideraron un tipo de categorías monoidales simétricas conocidas como categorías de Petri . ^[5]

Una de las cosas que hace interesantes a las redes de Petri es que proporcionan un equilibrio entre la capacidad 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 costosas de determinar en el caso general. Se han estudiado varias subclases de redes de Petri que aún pueden modelar clases interesantes de sistemas concurrentes, mientras que estas determinaciones se vuelven más fáciles.

Una descripción general de tales problemas de decisión , con resultados de decidibilidad y complejidad para redes de Petri y algunas subclases, se puede encontrar en Esparza y ​​Nielsen (1995). ^[6]

El problema de alcanzabilidad de las redes de Petri es decidir, dada una red de Petri N y una marca M , si .${\displaystyle M\in R(N)}$

Se trata de recorrer el gráfico de accesibilidad definido anteriormente hasta que se alcance la marca solicitada o hasta que ya no se pueda encontrar. Esto es más difícil de lo que parece a primera vista: el gráfico de accesibilidad suele ser infinito y no es fácil determinar cuándo es seguro detenerse.

De hecho, se demostró que este problema era EXPSPACE -hard ^[7] años antes de que se demostrara que era decidible (Mayr, 1981). Se siguen publicando artículos sobre cómo resolverlo de manera eficiente. ^[8] En 2018, Czerwiński et al. mejoraron el límite inferior y demostraron que el problema no es ELEMENTARY . ^[9] En 2021, se demostró que este problema no era recursivo primitivo , de forma independiente por Jerome Leroux ^[10] y por Wojciech Czerwiński y Łukasz Orlikowski. ^[11] Estos resultados cierran así la brecha de complejidad de larga data.

Si bien la alcanzabilidad 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 suele utilizar junto con el método de tabla para demostrar que dichos estados no se pueden alcanzar. La lógica temporal lineal utiliza la técnica de semidecisión para determinar si, en efecto, se puede alcanzar un estado, encontrando un conjunto de condiciones necesarias para que se alcance el estado y luego demostrando que esas condiciones no se pueden satisfacer.

Las redes de Petri pueden describirse como poseedoras de distintos grados de vitalidad . Una red de Petri se denomina -viva si y solo si todas sus transiciones son -vivas, donde una transición es${\displaystyle L_{1}-L_{4}}$${\displaystyle (N,M_{0})}$${\displaystyle L_{k}}$${\displaystyle L_{k}}$

• muerto , si nunca puede disparar, es decir, no está en ninguna secuencia de disparo en${\displaystyle L(N,M_{0})}$
• ${\displaystyle L_{1}}$-vivo ( potencialmente disparable ), si y sólo si puede disparar, es decir, está en alguna secuencia de disparo en${\displaystyle L(N,M_{0})}$
• ${\displaystyle L_{2}}$-vivo si puede dispararse con una frecuencia arbitraria, es decir, si por cada entero positivo k , ocurre al menos k veces en alguna secuencia de disparo en${\displaystyle L(N,M_{0})}$
• ${\displaystyle L_{3}}$-vivo si puede dispararse infinitamente a menudo, es decir, si hay una secuencia de disparo fija (necesariamente infinita) en la que para cada entero positivo k , la transición ocurre al menos k veces,${\displaystyle L_{3}}$
• ${\displaystyle L_{4}}$-live ( vivo ) si siempre puede disparar, es decir, está - vivo en cada marca alcanzable en${\displaystyle L_{1}}$${\displaystyle R(N,M_{0})}$

Téngase en cuenta que estos son requisitos cada vez más estrictos: -vivacidad implica -vivacidad, por ejemplo .${\displaystyle L_{j+1}}$${\displaystyle L_{j}}$${\textstyle \textstyle {j\in {1,2,3}}}$

Estas definiciones están de acuerdo con la descripción general de Murata, ^[12] que además utiliza -vivo como término para muerto .${\displaystyle L_{0}}$

Un lugar en una red de Petri se llama k-limitado si no contiene más de k tokens en todas las marcas alcanzables, incluida la marca inicial; se dice que es seguro si está 1-limitado; es acotado si está k-limitado para algún k .

Una red de Petri (marcada) se denomina k -limitada, segura o acotada cuando todos sus lugares lo son. Una red de Petri (grafo) se denomina (estructuralmente) acotada si está acotada para cada posible marcación inicial.

Una red de Petri está acotada si y sólo si su gráfico de alcanzabilidad es finito.

La acotación se puede decidir observando la cobertura , construyendo el árbol de Karp -Miller.

Puede resultar útil imponer explícitamente un límite a los lugares de una red determinada. Esto se puede utilizar para modelar recursos limitados del sistema.

Algunas definiciones de redes de Petri permiten esto explícitamente como una característica sintáctica. ^[13] Formalmente, las redes de Petri con capacidades de lugar se pueden definir como tuplas , donde es una red de Petri, una asignación de capacidades a (algunos o todos) los 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 tokens.${\displaystyle (S,T,W,C,M_{0})}$${\displaystyle (S,T,W,M_{0})}$${\displaystyle C:P\rightarrow \!\!\!\shortmid \mathbb {N} }$

Por ejemplo, si en la red N a ambos lugares se les asigna capacidad 2, obtenemos una red de Petri con capacidades de lugar, digamos N2 ; su gráfico de alcanzabilidad se muestra a la derecha.

Alternativamente, los lugares pueden delimitarse extendiendo la red. Para ser exactos, un lugar puede delimitarse mediante k añadiéndole un "contralugar" con flujo opuesto al del lugar y añadiendo tokens para que el total en ambos lugares sea k .

Además de para eventos discretos, existen redes de Petri para procesos continuos e híbridos discretos-continuos ^[14] que son útiles en la teoría de control discreto, continuo e híbrido , ^[15] y relacionadas con autómatas discretos, continuos e híbridos .

Existen muchas extensiones de las redes de Petri. Algunas de ellas son completamente compatibles con la red de Petri original (por ejemplo, las redes de Petri coloreadas ), mientras que otras añaden propiedades que no se pueden modelar en el formalismo de la red de Petri original (por ejemplo, las redes de Petri cronometradas). Aunque los modelos compatibles con versiones anteriores no amplían la capacidad computacional de las redes de Petri, pueden tener representaciones más sucintas y resultar más convenientes para el modelado. ^[16] Las extensiones que no se pueden transformar en redes de Petri son a veces muy potentes, pero normalmente 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 redes de Petri coloreadas, redes de Petri jerárquicas como Redes dentro de redes y todas las demás extensiones esbozadas en esta sección. El término también se utiliza específicamente para el tipo de redes coloreadas admitidas por CPN Tools .

A continuación se muestra 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 alcanzabilidad sea indecidible, ^[17] mientras que algunas otras propiedades, como la terminación, siguen siendo decidibles; ^[18]
  • Un arco inhibidor impone la condición previa de que la transición solo puede activarse cuando el lugar está vacío; esto permite que se expresen cálculos arbitrarios sobre números de tokens, lo que hace que el formalismo sea completo de Turing e implica la existencia de una red universal. ^[19]
• En una red de Petri estándar, los tokens son indistinguibles. En una red de Petri coloreada , cada token tiene un valor. ^[20] En herramientas populares para redes de Petri coloreadas como CPN Tools , los valores de los tokens están tipificados y se pueden probar (usando expresiones de protección ) y manipular con un lenguaje de programación funcional . Una subsidiaria de las redes de Petri coloreadas son las redes de Petri bien formadas , donde las expresiones de arco y protección están restringidas para facilitar el análisis de la red.
• Otra extensión popular de las redes de Petri es la jerarquía, que Fehling estudió en forma de diferentes vistas que admiten niveles de refinamiento y abstracción. 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. Véase ^[21] para una introducción informal a las redes de Petri de objetos.
• Un sistema de adición vectorial 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. Consideremos un autómata de estados finitos donde cada transición está etiquetada por una transición de la red de Petri. La red de Petri se sincroniza entonces con el autómata de estados finitos, es decir, una transición en el autómata se toma al mismo tiempo que la transición correspondiente en la red de Petri. Solo es posible tomar una transición en el autómata si la transición correspondiente en la red de Petri está habilitada, y solo es posible activar 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 suele formularse de forma ligeramente diferente).
• Las redes de Petri priorizadas añaden prioridades a las transiciones, por lo que una transición no puede activarse si se habilita una transición de mayor prioridad (es decir, puede activarse). Por lo tanto, las transiciones se encuentran en grupos de prioridad y, por ejemplo, el grupo de prioridad 3 solo puede activarse si se deshabilitan todas las transiciones en los grupos 1 y 2. Dentro de un grupo de prioridad, la activación sigue siendo no 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 use la red). Sin embargo, en ciertos casos surge la necesidad de modelar también el tiempo, no solo la estructura de un modelo. Para estos casos, han evolucionado las redes de Petri cronometradas, donde hay transiciones que son cronometradas y posiblemente transiciones que no lo son (si las hay, las transiciones que no son cronometradas tienen una prioridad más alta 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 alcanzabilidad de las redes se puede usar como una cadena de Markov de tiempo continuo (CTMC).
• Las redes de Petri dualistas (dP-Nets) son una extensión de las redes de Petri desarrollada por E. Dawis, et al. ^[22] para representar mejor los procesos del mundo real. Las dP-Nets equilibran la dualidad de cambio/no cambio, acción/pasividad, (transformación) tiempo/espacio, etc., entre los constructos bipartitos de las redes de Petri de transformación y lugar, lo que da como resultado la característica única de marcado de transformación , es decir, cuando la transformación está "funcionando", está marcada. Esto permite que la transformación se active (o se marque) varias veces, lo que representa el comportamiento del mundo real del rendimiento del proceso. El marcado de la transformación supone 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. Las dP-Nets también explotan el poder de la abstracción jerárquica de las redes de Petri 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 ^[23] , donde los requisitos de desarrollo se organizan en torno a la estructura del sistema diseñado.

Existen 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, resulta más difícil utilizar herramientas estándar para evaluar ciertas propiedades de la red. Por este motivo, es una buena idea utilizar el tipo de red más simple posible para una tarea de modelado determinada.

En lugar de ampliar el formalismo de las redes de Petri, también podemos intentar restringirlo y observar tipos particulares de redes de Petri, que se obtienen al restringir la sintaxis de una manera particular. Las redes de Petri ordinarias son las redes en las que todos los pesos de arco son 1. Si restringimos aún más, los siguientes tipos de redes de Petri ordinarias se utilizan y estudian comúnmente:

1. En una máquina de estados (SM), cada transición tiene un arco de entrada y un arco de salida, y todas las marcas tienen exactamente un token. En consecuencia, no puede haber concurrencia , pero puede haber conflicto (es decir, no determinismo ): matemáticamente,${\displaystyle \forall t\in T:|t^{\bullet }|=|{}^{\bullet }t|=1}$
2. En un grafo marcado (MG), cada lugar tiene un arco de entrada y un arco de salida. Esto significa que no puede haber conflicto , pero sí concurrencia: matemáticamente,${\displaystyle \forall s\in S:|s^{\bullet }|=|{}^{\bullet }s|=1}$
3. En una red de libre elección (CF), cada arco de un lugar a una transición es el único arco de ese lugar o el único arco a esa transición, es decir, puede haber concurrencia y conflicto, pero no al mismo tiempo : matemáticamente,${\displaystyle \forall s\in S:(|s^{\bullet }|\leq 1)\vee ({}^{\bullet }(s^{\bullet })=\{s\})}$
4. Elección libre extendida (EFC): una red de Petri que puede transformarse en una FC .
5. En una red de elección asimétrica (CA), pueden ocurrir concurrencia y conflicto (en suma, confusión ), pero no simétricamente: matemáticamente,${\displaystyle \forall s_{1},s_{2}\in S:(s_{1}{}^{\bullet }\cap s_{2}{}^{\bullet }\neq \emptyset )\to [(s_{1}{}^{\bullet }\subseteq s_{2}{}^{\bullet })\vee (s_{2}{}^{\bullet }\subseteq s_{1}{}^{\bullet })]}$

Las redes de flujo de trabajo (WF-nets) son una subclase de las redes de Petri que pretenden modelar el flujo de trabajo de las actividades del proceso. ^[24] Las transiciones de las WF-nets se asignan a tareas o actividades, y los lugares se asignan a las condiciones previas o posteriores. Las WF-nets tienen requisitos estructurales y operativos adicionales, principalmente la adición de un único lugar de entrada (fuente) sin transiciones previas, y un lugar de salida (sumidero) sin transiciones posteriores. En consecuencia, se pueden definir marcas de inicio y finalización que representan el estado del proceso.

Las redes WF tienen la propiedad de solidez , ^[24] lo 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 destino (definido como una red WF de sonido k ). Además, todas las transiciones en el proceso podrían activarse (es decir, para cada transición hay un estado alcanzable en el que la transición está habilitada). Una red WF de sonido general (G-sonido) se define como k -sonido para cada k > 0. ^[25]

Un camino dirigido en la red de Petri se define como la secuencia de nodos (lugares y transiciones) unidos por arcos dirigidos. Un camino elemental incluye cada nodo de la secuencia solo una vez.

Una red de Petri bien manejada es una red en la que no existen caminos elementales completamente distintos entre un lugar y una transición (o una transición y un lugar), es decir, si hay dos caminos entre el par de nodos, entonces estos caminos comparten un nodo. Una red de Petri acíclica bien manejada es sólida (G-sound). ^[26]

La red WF extendida es una red de Petri que se compone de una red WF con una transición adicional t (transición de retroalimentación). El lugar de destino está conectado como el lugar de entrada de la transición t y el lugar de origen como su lugar de salida. La activación de la transición provoca la iteración del proceso (nótese que la red WF extendida no es una red WF). ^[24]

WRI (Well-handled with Regular Iteration) WF-net, es una red WF acíclica extendida y bien manejada. WRI-WF-net se puede construir como una composición de redes, es decir, reemplazando una transición dentro de una red WRI-WF con una subred que es una red WRI-WF. El resultado también es una red WRI-WF. Las redes WRI-WF son G-sound, ^[26] por lo tanto, al usar solo los bloques de construcción de WRI-WF-net, se pueden obtener redes WF que son G-sound por construcción.

La matriz de estructura de diseño (DSM) puede modelar las relaciones de los procesos y utilizarse para la planificación de los mismos. Las redes DSM son la materializació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 garantiza la solidez de la red resultante.

Se han propuesto otras formas de modelar la computación concurrente, incluidos los sistemas de adición de vectores , las máquinas de estados finitos comunicantes , las redes de procesos de Kahn , el álgebra de procesos , el modelo de actor y la teoría de trazas . ^[27] Diferentes modelos proporcionan 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. ^[28]

• Cálculo diferencial booleano ^[29]
• Modelado de procesos de negocio ^{[30] [31]}
• Biología computacional ^{[32] [33]}
• Programación concurrente ^[34]
• Ingeniería de control ^{[15] [35] [36]}
• Análisis de datos ^[37]
• Diagnóstico (inteligencia artificial) ^[38]
• Control de procesos discretos ^{[39] [40] [41]}
• Teoría de juegos ^[42]
• Diseño de hardware ^{[43] [44] [45]}
• Redes de procesos de Kahn ^[46]
• Modelado de procesos ^{[47] [48] [49]}
• Ingeniería de confiabilidad ^{[50] [51]}
• Simulación ^[30]
• Diseño de software ^[14]
• Sistemas de gestión de flujo de trabajo ^{[52] [48] [49]}

• Máquina de estados finitos
• Aprendizaje automático
• Lenguaje de marcado de red de Petri
• Petriscript
• Arquitectura de procesos
• Redes de Petri cortadas
• Sistemas de adición de vectores

Wikimedia Commons alberga una categoría multimedia sobre Redes de Petri .

• Cardoso, Janette; Camargo, Heloísa (1999). Borrosidad en las redes de Petri . Editorial Física. 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 de un controlador lógico embebido con deducción por computadora en lógica temporal". Przegląd 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). "Petri Nets". Encuestas de computación de ACM . 9 (3): 223–252. doi :10.1145/356698.356702. hdl : 10338.dmlcz/135597 . S2CID  3605804.
• Peterson, James Lyle (1981). Teoría de redes 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). 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 redes de Petri . Libros a pedido. ISBN 978-3-8311-1330-9.
• Zaitsev, Dmitry (2013). Clanes de redes de Petri: verificación de protocolos y evaluación del rendimiento de las redes. LAP LAMBERT Academic Publishing. ISBN 978-3-659-42228-7.
• Zhou, Mengchu ; Dicesare, Frank (1993). Síntesis de redes de Petri para el control de eventos discretos de sistemas de fabricación . Kluwer Academic Publishers. ISBN 978-0-7923-9289-7.
• Zhou, Mengchu ; Venkatesh, Kurapati (1998). Modelado, simulación y control de sistemas de fabricación flexible: un enfoque de red de Petri . World Scientific Publishing. ISBN 978-981-02-3029-6.
• Xue-Guo, Xu (2019). "Redes de Petri difusas de imágenes para la representación y adquisición de conocimiento al considerar opiniones conflictivas". Applied Sciences . 9 (5): 983. doi : 10.3390/app9050983 .