Active learning of symbolic automata over rational numbers
Loading...
Date
2025
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
El aprendizaje de autómatas tiene muchas aplicaciones en inteligencia artificial e ingeniería de software. Un aporte clave para estas aplicaciones es el algoritmo L⇤, introducido por (Angluin, 1987). El algoritmo L⇤ aprende autómatas deterministas (DFAs, en inglés) en tiempo polinomial cuando se provee un profesor MAT (minimally adequeate teacher). Desafortunadamente, el algoritmmo L⇤ solo puede aprender DF As sobre alfabetos finitos, lo que limita su aplicacion en escenarios más complejos. En este trabajo, extendemos el algoritmo L⇤ para aprender autómatas simbólicos, aquellos en que sus transiciones pueden usar predicados de desigualdad sobre numeros racionales, es decir, sobre alfabetos infinitos y densos. Nuestro resultado logra que el algoritmo L⇤ pueda ser aplicable en nuevos escenarios reales como RGX (reales) y series de tiempo. En adición, nuestro algoritmo propuesto es óptimo dado que realiza un número lineal de consultas al profesor con respecto al número de transiciones y el tamaño de la representación de los predicados.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2025.