Algoritmos para el conjunto de mínima cobertura de las Redes de Petri

Abstract

Desde que Carl Adam Petri definió las Redes de Petri en los años 60, estas han sido una herramienta muy utilizada para modelar y analizar sistemas concurrentes, sirviendo como una representación gráfica que describe la dinámica de sistemas complejos, lo que las convierte en un recurso esencial en las Ciencias de la Computación. Uno de los problemas centrales en el análisis de redes de Petri es la determinación de su comportamiento y su capacidad de alcanzar diferentes estados. El árbol de cobertura, es una estructura de datos crucial en este contexto, ya que representa de manera eficiente una aproximación compacta útil del conjunto de estados a los que puede llegar una red de Petri durante su ejecución. Sin embargo, calcular el árbol de mínima cobertura de una red de Petri, que proporciona una visión más concisa y simplificada de su comportamiento, es una tarea computacionalmente desafiante. En este trabajo exploraremos los algoritmos de Finkel, CovProc, un algoritmo que computa el conjunto de mínima cobertura utilizando el algoritmo de Tarjan (StackProc), Poda-Monótona y MinCov, desarrollados con el propósito de calcular el conjunto de mínima cobertura de una Red de Petri. Cada uno de estos enfoques ha sido diseñado para abordar este problema desde una perspectiva diferente, buscando optimizar la eficiencia y la precisión del resultado. Estos cuatro algoritmos se examinarán en detalle presentando sus fundamentos teóricos y analizando su eficacia y eficiencia. Así, tendremos una visión completa de los algoritmos que se han desarrollado para calcular el conjunto de mínima cobertura de las redes de Petri.Since Carl Adam Petri defined Petri Nets in the 1960s, they have been a highly useful tool for modeling and analyzing concurrent systems, serving as a graphical representation that describes the dynamics of complex systems, making them an essential asset in computer science research. One of the central challenges in the analysis of Petri nets is determining their behavior and their ability to reach different states. The coverability tree is a crucial data structure in this context as it efficiently represents a compact approximation of the set of states a Petri net can reach during its execution. However, calculating the minimal coverability tree of a Petri net, which provides a more concise and simplified view of its behavior, is a computationally challenging task. In this work, we will explore the algorithms of Finkel, CovProc, a minimal coverability set algorithm that uses Tarjan’s algorithm (StackProc), Monotonic-Prunning and MinCov developed for the purpose of calculating the minimal coverability set of a Petri Net. Each of these approaches has been designed to address this problem from a different perspective, aiming to optimize efficiency and result accuracy. These five algorithms will be examined in detail, presenting their theoretical foundations and analyzing their effectiveness and efficiency. Thus, we will have a comprehensive view of the algorithms that have been developed to calculate the minimal coverability set of Petri nets.