Resumen Técnico: La Complejidad de las Cerraduras Descendentes de los Lenguajes Indexados

Enunciado del Problema

El artículo aborda la complejidad computacional de la construcción de cerraduras descendentes para lenguajes indexados. La cerradura descendente de un lenguaje $L$, denotada $L^\downarrow$, es el conjunto de todas las subpalabras dispersas de las palabras en $L$. Según el Lema de Higman, $L^\downarrow$ es siempre un lenguaje regular, lo que la convierte en una sobreaproximación regular crucial utilizada en la verificación de sistemas de estado infinito (por ejemplo, comprobación de modelos de orden superior, programas asíncronos y sistemas de canales con pérdidas).

Si bien la computabilidad de las cerraduras descendentes para lenguajes indexados (equivalentes a autómatas de pila de orden 2 o 2-PDA) se estableció en 2015 mediante un algoritmo general basado en cuasi-órdenes bien, los límites de complejidad para esta construcción permanecieron como un problema abierto. Específicamente, se desconocía si existía una construcción primitivo-recursiva, y no se conocían límites superiores ni inferiores sobre el tamaño de los autómatas resultantes. Antes de este trabajo, el mejor límite inferior conocido para el tamaño de un autómata finito no determinista (AFN) para la cerradura descendente de un lenguaje indexado era doblemente exponencial, y la complejidad de problemas de decisión como la inclusión y la equivalencia de cerraduras descendentes se sabía que era al menos co-2-NEXP-dura.

Metodología

Los autores resuelven este problema abierto proporcionando límites superiores e inferiores ajustados (asintóticamente coincidentes). Su enfoque se basa en una abstracción algebraica novedosa del contenido de la pila para transformar gramáticas indexadas en gramáticas libres de contexto (GLC) preservando la cerradura descendente.

1. Productividad y Anotación

La construcción comienza asegurando que la gramática indexada de entrada sea productiva (cada forma sentencial puede derivar una palabra terminal). Los autores introducen una versión anotada de la gramática donde los símbolos de pila se emparejan con conjuntos de no terminales que pueden derivar palabras terminales desde esa configuración de pila. Esto evita la generación de términos "muertos" que no pueden contribuir al lenguaje, una propiedad esencial para preservar la cerradura descendente durante las transformaciones posteriores.

2. El Monoide de Pila y Resúmenes

La innovación técnica central involucra la teoría de semigrupos finitos. Los autores definen un monoide de pila $M$ (un monoide finito de matrices booleanas) que codifica el comportamiento de las operaciones de pila (empujar y sacar) con respecto a los no terminales de la gramática.

• Resúmenes: Utilizan avances recientes en la teoría de semigrupos (específicamente resultados de Jecker y Gimbert et al.) para calcular resúmenes de palabras de pila arbitrariamente largas. Un resumen es una representación comprimida de una palabra de pila que retiene suficiente información para determinar el resultado de las operaciones de empuje/saqueo con respecto al monoide $M$.
• Bombeo y Omisión: Los autores introducen dos nuevas reglas de derivación, bombear y omitir, que permiten la extensión y reducción de infixos de pila que se mapean al mismo elemento idempotente en el monoide. Demuestran que estas reglas no alteran la cerradura descendente del lenguaje.
• Compresión: Al aplicar estas reglas, muestran que cualquier contenido de pila puede comprimirse en un resumen de tamaño acotado (exponencial en el tamaño de la gramática). Esta compresión pierde efectivamente información sobre el contenido exacto de la pila, pero preserva la cerradura descendente.

3. Reducción a Gramáticas Libres de Contexto

Utilizando estos resúmenes, los autores construyen una gramática libre de contexto (GLC) $G_{CFG}$ que simula la gramática indexada original $G$. En $G_{CFG}$, los contenidos de pila de la gramática indexada se reemplazan por sus resúmenes.

• Los no terminales de $G_{CFG}$ son tripletes $(A, X, \sigma)$, donde $A$ es un no terminal, $X$ es un conjunto de no terminales, y $\sigma$ es un resumen factible.
• Las operaciones de empuje y sacado en la gramática original se simulan mediante operaciones sobre resúmenes (utilizando las relaciones push y pop definidas en el monoide).
• Los autores demuestran que $L(G_{CFG})^\downarrow = L(G)^\downarrow$.

4. Análisis de Complejidad

Dado que el tamaño de un resumen está acotado exponencialmente en el tamaño de la gramática, la GLC resultante $G_{CFG}$ tiene un tamaño doble exponencial. Los algoritmos existentes para calcular cerraduras descendentes de GLC producen un AFN de tamaño exponencial relativo a la GLC. En consecuencia, la composición produce un AFN para $L(G)^\downarrow$ de tamaño triple exponencial.

Para autómatas finitos deterministas (AFD), la construcción de subconjuntos estándar aplicada al AFN triple exponencial resulta en un límite superior cuádruple exponencial.

Contribuciones y Resultados Clave

Límites Superiores

• Tamaño del AFN: Dada una gramática indexada de tamaño $n$, un AFN para su cerradura descendente puede calcularse en tiempo triple exponencial y tiene un tamaño de a lo sumo triple exponencial ($O(\exp_3(n))$).
• Tamaño del AFD: Un AFD para la cerradura descendente puede construirse con un tamaño de a lo sumo cuádruple exponencial ($O(\exp_4(n))$).
• Problemas de Decisión: Los problemas de inclusión de cerradura descendente ($L_1^\downarrow \subseteq L_2^\downarrow$) y equivalencia ($L_1^\downarrow = L_2^\downarrow$) para lenguajes indexados son co-3-NEXP-completos.

Límites Inferiores

Los autores proporcionan límites inferiores coincidentes, demostrando la precisión de sus límites superiores:

• Límite Inferior del AFN: Existe una familia de gramáticas indexadas de tamaño polinómico tal que cualquier AFN para su cerradura descendente requiere al menos estados triples exponenciales. Esto se logra construyendo una gramática que genera el lenguaje $\{a^{\exp_3(n)}\}$.
• Límite Inferior del AFD: Existe una familia de gramáticas indexadas tal que cualquier AFD para su cerradura descendente requiere al menos estados cuádruples exponenciales.
• Umbral de Bombeo: Los resultados implican que el umbral de bombeo para gramáticas indexadas (la longitud máxima de una palabra en un lenguaje indexado finito de tamaño $n$) crece al menos triple exponencialmente, corrigiendo una afirmación previa de un límite doblemente exponencial encontrada en la literatura.

Significado

El artículo resuelve un problema abierto de larga data sobre la complejidad de las cerraduras descendentes para lenguajes indexados.

1. Límites Ajustados: Establece que la complejidad es estrictamente mayor que para los lenguajes libres de contexto (que son doblemente exponenciales para AFN) pero menor que la torre general de exponenciales a menudo asociada con sistemas de orden superior de orden $k > 2$. El salto de doble a triple exponencial para lenguajes indexados (orden 2) es inesperado dado el crecimiento lineal de la complejidad para otros problemas (como la vacuidad) con respecto al orden del autómata de pila.
2. Viabilidad Algorítmica: Confirma que existe una construcción primitivo-recursiva, resolviendo la cuestión de si el problema es meramente computable o efectivamente construible dentro de una clase de complejidad específica.
3. Avance Metodológico: La técnica de utilizar resúmenes basados en semigrupos para comprimir contenidos de pila mientras se preservan las cerraduras descendentes ofrece una nueva herramienta para analizar sistemas de orden superior, potencialmente aplicable a clases más amplias de sistemas de estado infinito.

Los autores enfatizan que sus resultados se derivan de una transformación constructiva de gramáticas indexadas a GLC, aprovechando las propiedades algebraicas del monoide de pila para gestionar la naturaleza ilimitada de las pilas de una manera que preserva la estructura de subpalabras esencial para las cerraduras descendentes.