Comparación de MILP, SAT Y ASP para la spintesis de autómatas mínimos a partir de trazas
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
En este trabajo, comparamos tres enfoques principales para la síntesis de autómatas finitos deterministas minimales (DFA) a partir de trazas etiquetadas positiva y negativamente: Programación Lineal Entera Mixta (MILP), resolución de problemas SAT y Programación de Conjuntos de Respuestas (ASP). Adaptamos modelos SAT existentes, desarrollamos nuevas codificaciones basadas en MILP y ASP, y creamos un conjunto de datos inspirado en la competencia StaMinA para evaluar el rendimiento de los modelos. Los resultados muestran que los enfoques basados en SAT son consistentemente superiores, resolviendo problemas tanto simples como complejos con mayor eficiencia. Los modelos basados en ASP presentan un rendimiento competitivo bajo configuraciones específicas, mientras que MILP mostró limitaciones en comparación. Este estudio destaca la importancia de las optimizaciones en modelos basados en ASP y su potencial para aplicaciones futuras, como la extensión a autómatas no deterministas y otros problemas de optimización discreta.
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2025