Resultados de investigación
Pedro Valero, investigador del Instituto IMDEA Sofware, supervisado por Pierre Ganty, defendió su tesis doctoral con el título “On the use of Quasiorders in Formal Language Theory” el pasado 20 de julio. La tesis fue presentada como requisito para la obtención del título de Doctorado en Software, Sistemas y Computación.
Los preórdenes en palabras, es decir, relaciones binarias entre palabras, han demostrado ser útiles para razonar sobre lenguajes formales a nivel teórico. Por ejemplo, los preórdenes han sido utilizado para caracterizar la clase de lenguajes regulares y para mostrar que todas las soluciones máximas de ciertos sistemas de ecuaciones en lenguajes son regulares.
En su tesis, Pedro muestra que los preórdenes también tienen aplicaciones prácticas, situándolos en el centro de varios algoritmos.
En concreto, en su tesis, Pedro usa preórdenes para dar un nuevo enfoque a dos problemas fundamentales en la Teoría de Lenguajes Formales: decidir la inclusión entre lenguajes, con aplicación a la búsqueda en textos comprimidos, y manipular la representación de lenguajes regulares como los autómatas finitos.
El Problema de la Inclusión de Lenguajes
En su investigación, Pedro considera el problema de decidir L1 ⊆ L2, donde L1 es un lenguaje independiente de contexto y L2 es un lenguaje regular. Este problema se puede resolver comprobando si una sobreaproximación de L1 está incluida en el lenguaje L2, por lo que el problema es decidible siempre y cuando la sobreaproximación sea completa (es decir, la imprecisión de la aproximación no produzca falsas alarmas) y evite cadenas infinitas ascendentes (es decir, garantice que la iteración de punto fijo termina).
Esta sobreaproximación se define usando preórdenes de modo que la aproximación del lenguaje L1 contiene todas las palabras “mayores o iguales que” alguna palabra de L1. En su tesis, Pedro define una serie de preórdenes con los que derivar, de manera sistemática, algoritmos de decisión para diferentes problemas de inclusión de lenguajes como la inclusión entre lenguajes regulares o la inclusión de lenguajes independientes de contexto en lenguajes regulares.
Algunos de los algoritmos obtenidos mediante esta técnica coinciden con algoritmos populares, como los llamados ‘antichains algorithms’, mientras otros corresponden con algoritmos nuevos de punto fijo.
Búsqueda en textos comprimidos
En segundo lugar, la tesis aplica el algoritmo de decisión de inclusión entre lenguajes al caso concreto en que L1 es un lenguaje descrito por una gramática que genera una única palabra y L2 es un lenguaje regular definido por un autómata o expresión regular. El algoritmo resultante puede emplearse para decidir si un texto comprimido mediante una gramática contiene, o no, una coincidencia de una expresión regular dada.
Pedro muestra cómo extender este algoritmo para contar las líneas del texto comprimido que contienen coincidencias de la expresión regular. De este modo, se obtiene un algoritmo que opera en tiempo linear respecto al tamaño del texto comprimido el cual, por definición, puede ser exponencialmente más pequeño que el texto original.
Además, la tesis describe las estructuras de datos necesarias para que el algoritmo opere en tiempo óptimo y presenta una implementación –zearch– que resulta hasta un 40% más rápida que las mejores implementaciones del método estándar de descompresión y búsqueda.
Autómatas Residuales
Por último, en su tesis, Pedro presenta una serie de autómatas parametrizados por preórdenes que permiten mejorar la compresión de la clase de autómatas residuales (abreviados como RFA).
Estos autómatas parametrizados permiten generalizar el método de double-reversal para RFAs de manera similar a su generalización para el caso de autómatas deterministas y dar un nuevo enfoque a NL*, un algoritmo de aprendizaje de RFAs.
Estos resultados evidencian que los preórdenes juegan el mismo papel para los autómatas residuales que las congruencias para los deterministas.
