Redes de Petri, algoritmo para la construcción de árboles de mínima cobertura

En el ámbito del diseño de sistemas embebidos críticos, donde predominan las reacciones a eventos y la lógica basada en acciones, las Redes de Petri emergen como una herramienta de modelado esencial. Mediante la implementación de una ecuación de estado extendida, es posible capturar la lógica de est...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Ventre, Luis Orlando, Micolini, Orlando, Venezuela, Gabriel, Ludemann, Mauricio
Formato: Objeto de conferencia
Lenguaje:Español
Publicado: 2024
Materias:
Ciencias Informáticas
Redes de Petri
Árboles de Cobertura
Sistemas Embebidos
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/178814
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-178814
record_format dspace
spelling I19-R120-10915-1788142025-05-08T20:07:53Z http://sedici.unlp.edu.ar/handle/10915/178814 Redes de Petri, algoritmo para la construcción de árboles de mínima cobertura Ventre, Luis Orlando Micolini, Orlando Venezuela, Gabriel Ludemann, Mauricio 2024-08 2024 2025-05-08T12:52:42Z es Ciencias Informáticas Redes de Petri Árboles de Cobertura Sistemas Embebidos En el ámbito del diseño de sistemas embebidos críticos, donde predominan las reacciones a eventos y la lógica basada en acciones, las Redes de Petri emergen como una herramienta de modelado esencial. Mediante la implementación de una ecuación de estado extendida, es posible capturar la lógica de estos sistemas. El modelo lógico resultante se ejecuta a través de un monitor que integra la lógica (Red de Petri), la política (gestión de conflictos) y las acciones, formando un sistema heterogéneo. Esta integración mejora la capacidad del sistema para ser verificado mediante formalismos matemáticos basados en el modelo empleado. En este contexto, la verificación de propiedades importantes de las RdP, como la cobertura, la acotación, la alcanzabilidad y la vivacidad, se realiza utilizando árboles de cobertura, con un tiempo de verificación proporcional al tamaño del árbol. Por lo tanto, es crucial diseñar algoritmos que calculen el árbol de cobertura de manera eficiente. En este trabajo, presentamos una modificación del algoritmo de árbol de cobertura mínima, originalmente propuesto por Karp y Miller. Para hacer este cálculo, se memorizan las aceleraciones activándolas como transiciones ordinarias. Esta estrategia no solo asegura un límite predecible para el uso de memoria adicional —específicamente, un máximo de doble exponencial—, sino que también mejora la eficiencia operativa. La implementación de un prototipo de este algoritmo muestra su competitividad, presentando un uso reducido de memoria y tiempos de ejecución comparables a las herramientas más rápidas disponibles. Sociedad Argentina de Informática e Investigación Operativa Objeto de conferencia Objeto de conferencia http://creativecommons.org/licenses/by-nc-sa/4.0/ Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) application/pdf 28-39
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
Redes de Petri
Árboles de Cobertura
Sistemas Embebidos
spellingShingle Ciencias Informáticas
Redes de Petri
Árboles de Cobertura
Sistemas Embebidos
Ventre, Luis Orlando
Micolini, Orlando
Venezuela, Gabriel
Ludemann, Mauricio
Redes de Petri, algoritmo para la construcción de árboles de mínima cobertura
topic_facet Ciencias Informáticas
Redes de Petri
Árboles de Cobertura
Sistemas Embebidos
description En el ámbito del diseño de sistemas embebidos críticos, donde predominan las reacciones a eventos y la lógica basada en acciones, las Redes de Petri emergen como una herramienta de modelado esencial. Mediante la implementación de una ecuación de estado extendida, es posible capturar la lógica de estos sistemas. El modelo lógico resultante se ejecuta a través de un monitor que integra la lógica (Red de Petri), la política (gestión de conflictos) y las acciones, formando un sistema heterogéneo. Esta integración mejora la capacidad del sistema para ser verificado mediante formalismos matemáticos basados en el modelo empleado. En este contexto, la verificación de propiedades importantes de las RdP, como la cobertura, la acotación, la alcanzabilidad y la vivacidad, se realiza utilizando árboles de cobertura, con un tiempo de verificación proporcional al tamaño del árbol. Por lo tanto, es crucial diseñar algoritmos que calculen el árbol de cobertura de manera eficiente. En este trabajo, presentamos una modificación del algoritmo de árbol de cobertura mínima, originalmente propuesto por Karp y Miller. Para hacer este cálculo, se memorizan las aceleraciones activándolas como transiciones ordinarias. Esta estrategia no solo asegura un límite predecible para el uso de memoria adicional —específicamente, un máximo de doble exponencial—, sino que también mejora la eficiencia operativa. La implementación de un prototipo de este algoritmo muestra su competitividad, presentando un uso reducido de memoria y tiempos de ejecución comparables a las herramientas más rápidas disponibles.
format Objeto de conferencia
Objeto de conferencia
author Ventre, Luis Orlando
Micolini, Orlando
Venezuela, Gabriel
Ludemann, Mauricio
author_facet Ventre, Luis Orlando
Micolini, Orlando
Venezuela, Gabriel
Ludemann, Mauricio
author_sort Ventre, Luis Orlando
title Redes de Petri, algoritmo para la construcción de árboles de mínima cobertura
title_short Redes de Petri, algoritmo para la construcción de árboles de mínima cobertura
title_full Redes de Petri, algoritmo para la construcción de árboles de mínima cobertura
title_fullStr Redes de Petri, algoritmo para la construcción de árboles de mínima cobertura
title_full_unstemmed Redes de Petri, algoritmo para la construcción de árboles de mínima cobertura
title_sort redes de petri, algoritmo para la construcción de árboles de mínima cobertura
publishDate 2024
url http://sedici.unlp.edu.ar/handle/10915/178814
work_keys_str_mv AT ventreluisorlando redesdepetrialgoritmoparalaconstrucciondearbolesdeminimacobertura
AT micoliniorlando redesdepetrialgoritmoparalaconstrucciondearbolesdeminimacobertura
AT venezuelagabriel redesdepetrialgoritmoparalaconstrucciondearbolesdeminimacobertura
AT ludemannmauricio redesdepetrialgoritmoparalaconstrucciondearbolesdeminimacobertura
_version_ 1847925378676424704

Ejemplares similares