Browsing by Author "Medina Jorquera, Alex Pavel"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Comparación de MILP, SAT Y ASP para la síntesis de autómatas mínimos a partir de trazas
    (2025) Medina Jorquera, Alex Pavel; Baier Aranda, Jorge Andrés; Toro Icarte, Rodrigo Andrés; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    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.