On the use of quasiorders in formal language theory

Resumen

En esta tesis, usamos preórdenes para dar un nuevo enfoque a dos problemas fundamentales en Teoría de Lenguajes Formales: decidir la inclusión entre lenguajes y manipular la representación de lenguajes regulares como autómatas finitos. En primer lugar, presentamos un esquema que, dado un preorden que satisface ciertos requisitos, nos permite derivar de manera sistemática algoritmos de decisión para la inclusión entre diferentes tipos de lenguajes. Partiendo de este esquema desarrollamos un algoritmo de búsqueda con expresiones regulares en textos comprimidos mediante gramáticas. Por último, presentamos una serie de autómatas, cuya definición depende de un preorden, que nos permite ofrecer un nuevo enfoque sobre la clase de autómatas residuales. # El Problema de la Inclusión de Lenguajes En primer lugar, estudiamos el problema de decidir L₁ ⊆ L₂, donde L₁ es un lenguaje independiente de contexto y L₂ es un lenguaje regular. Para resolver este problema, sobre-aproximamos los sucesivos pasos de la iteración de punto fijo que define el lenguaje L₁. Con ello, obtenemos una sobre-aproximación de L₁ y comprobamos si está incluida en el lenguaje L₂. Esta técnica funciona siempre y cuando la sobre-aproximació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). Para definir una sobre-aproximación que cumple estas condiciones, usamos un preorden. De este modo, la aproximación del lenguaje L₁ contiene todas las palabras ``mayores o iguales que'' alguna palabra de L₁. En concreto, definimos una serie de preórdenes que nos permiten 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 bien conocidos como los llamados antichains algorithms. Por otro lado, nuestra técnica también nos permite derivar algoritmos de punto fijo que, hasta donde sabemos, no han sido descritos anteriormente. # Búsqueda en textos comprimidos En segundo lugar, aplicamos nuestro algoritmo de decisión de inclusión entre lenguajes al problema L₁ ⊆ L₂, donde L₁ es un lenguaje descrito por una gramática que genera una única palabra y L₂ es un lenguaje regular definido por un autómata o expresión regular. De esta manera, obtenemos un algoritmo que nos permite decidir si un texto comprimido mediante una gramática contiene, o no, una coincidencia de una expresión regular dada. Posteriormente, modificamos este algoritmo para contar las líneas del texto comprimido que contienen coincidencias de la expresión regular. De este modo, obtenemos un algoritmo que opera en tiempo linear respecto del tamaño del texto comprimido el cual, por definición, puede ser exponencialmente más peque-ño que el texto original. Además, describimos las estructuras de datos necesarias para que nuestro algoritmo opere en tiempo óptimo y presentamos una implementación -zearch- que resulta hasta un 40% más rápida que las las mejores implementaciones del método estándar de descompresión y búsqueda. # Autómatas Residuales Finalmente presentamos una serie de autómatas parametrizados por preórdenes que nos permiten mejorar nuestra compresión de la clase de autómatas residuales (abreviados como RFA). Estos autómatas parametrizados nos permiten definir una nueva operación de residualization y demostrar que el método de double-reversal funciona para RFAs, es decir, residualizar un autómata cuyo reverso es residual da lugar al canonical RFA (un RFA de tamaño mínimo). Tras esto, generalizamos este método de forma similar a su generalización para el caso de autómatas deterministas. Por último, damos un nuevo enfoque a NL*, un algoritmo de aprendizaje de RFAs. Como conclusión, encontramos que los preórdenes juegan el mismo papel para los autómatas residuales que las congruencias para los deterministas.