Resultados de investigación
Los investigadores Pierre Ganty, Elena Gutiérrez y Pedro Valero han publicado recientemente “A Quasiorder-based Perspective in Residual Automata” presentado en MFCS 2020 (Mathematical Foundations of Computer Science)que tuvo lugar del 24 al 28 de agosto. Los tres investigadores del Instituto IMDEA Software proponen una visión diferente sobre una clase de máquinas de estado finito de gran relevancia en la práctica, los llamados “Autómatas Residuales”.
Para dar un poco de contexto, los autómatas residuales son los clásicos autómatas de estado finito (FSA en inglés), es decir, sistemas de transición con un número finito de estados que se utilizan para representar los llamados lenguajes regulares, uno de los objetos más estudiados en la teoría del lenguaje formal.
En realidad, los autómatas de estado finito son representaciones finitas de los lenguajes regulares, y esto puede no ser esclarecedor pero es bastante útil cuando los lenguajes que representan son infinitos!
Volviendo al objeto de estudio de la publicación, los autómatas residuales, entre los FSA generales, disfrutan de interesantes propiedades que los hacen útiles en aplicaciones como la inferencia de gramáticas.
El objetivo principal de la inferencia de gramáticas es encontrar un idioma de destino utilizando un conjunto finito de ejemplos de palabras en el idioma. En otras palabras, la inferencia gramatical es una técnica de aprendizaje automático (machine learning) mediante la cual aprendemos un lenguaje (posiblemente infinito) mediante solo una serie finita de palabras.
En este contexto, los autómatas residuales son herramientas útiles, ya que se ha demostrado que pueden representar muy concisamente (y de manera finita, ya que son FSA) el idioma de destino.
En este trabajo se estudian las propiedades de los autómatas residuales desde un punto de vista teórico. Es decir, utilizan el preorden como herramienta matemática para dar una nueva perspectiva sobre la construcción de los autómatas residuales. Las preórdenes son relaciones entre los elementos de un conjunto que satisfacen algunas propiedades. Por ejemplo, dado el conjunto de todos los números naturales N, la relación ≤, que relaciona dos elementos x e y si x ≤ y, es un preorden sobre N.
En este trabajo, definen las preórdenes sobre las palabras y las utilizan para construir autómatas residuales. Utilizando diferentes preórdenes construyen diferentes autómatas residuales, incluyendo el mínimo para algún lenguaje dado.
Concretamente, presentan una nueva operación de residualización y una versión general del método de Brzozowski para construir el autómata residual mínimo para un lenguaje dado. También aprovechamos esta técnica para ofrecer una nueva perspectiva sobre NL*, un algoritmo de aprendizaje en línea para autómatas residuales.
