Resultados de investigación
La investigadora del Instituto IMDEA Software, Elena Gutiérrez, supervisada por Pierre Ganty, defendió recientemente su tesis titulada: “New Perspectives on Classical Automata Constructions”.
En su tesis se centra en los modelos de autómatas de estado finito, autómatas de empuje y gramáticas sin contexto. Estos modelos han demostrado ser útiles para un amplio número de aplicaciones como la verificación de programas, tareas de procesamiento de lenguaje natural o técnicas de compresión de imágenes digitales. Estas aplicaciones se basan en gran medida en nociones teóricas del lenguaje donde, todavía hoy, hay muchas preguntas abiertas.
El objetivo de esta tesis es dar una nueva perspectiva teórica a un conjunto de problemas abiertos, que están en el centro de las construcciones clásicas de los autómatas y de los algoritmos bien establecidos.
La herramienta matemática para abordar estas cuestiones son las relaciones de equivalencia sobre las palabras como abstracciones de idiomas. Por lo tanto, en su trabajo estudia tres preguntas principales:
En esta tesis, ella apunta a obtener una mejor comprensión de la base teórica del método de doble reversión y su conexión con las técnicas basadas en la partición. Como resultado, proporciona un marco uniforme de construcciones de autómatas deterministas basadas en equivalencias de índices finitos sobre palabras que permiten dar una nueva prueba simple del método de doble reversión y arrojar luz sobre la relación entre este algoritmo y las técnicas basadas en la partición.
Su principal contribución es proporcionar una familia infinita de PDA definidos sobre un alfabeto de una sola letra que le permite extraer límites más bajos en el número de variables gramaticales de la CFG más pequeña.
En resumen, “en esta disertación aprovechamos las equivalencias de las palabras como abstracciones de idiomas. Más concretamente, estas abstracciones son aproximaciones regulares de los idiomas. Nuestros resultados sobre congruencias de índices finitos fomentan el estudio de otros tipos de aproximaciones regulares de lenguajes libres de contexto y el uso de nuestro marco para definir construcciones de autómatas basados en congruencias para su representación finita”, comentó Elena. Por otra parte, su trabajo sobre el supuesto de equivalencia de Parikh muestra que, a pesar de ser una versión relajada de la equivalencia del lenguaje que permite el análisis de ciertos sistemas complejos, cuando se comparan los PDA con los CFG la situación no es diferente a la de la equivalencia del lenguaje. Además, también establece la base para futuras direcciones en la extensión del Teorema de Parikh a los autómatas ponderados.
