Resumo Técnico: A Complexidade dos Fechamentos Descendentes de Linguagens Indexadas

Declaração do Problema

O artigo aborda a complexidade computacional da construção de fechamentos descendentes para linguagens indexadas. O fechamento descendente de uma linguagem $L$, denotado $L^\downarrow$, é o conjunto de todas as subsequências dispersas das palavras em $L$. Pelo Lema de Higman, $L^\downarrow$ é sempre uma linguagem regular, tornando-se uma superaproximação regular crucial utilizada na verificação de sistemas de estado infinito (por exemplo, verificação de modelos de ordem superior, programas assíncronos e sistemas de canais perdidos).

Embora a computabilidade dos fechamentos descendentes para linguagens indexadas (equivalentes a autômatos de pilha de ordem-2 ou 2-PDAs) tenha sido estabelecida em 2015 por meio de um algoritmo geral baseado em quasi-ordens bem-fundamentadas, os limites de complexidade para essa construção permaneceram um problema em aberto. Especificamente, era desconhecido se existia uma construção primitivo-recursiva, e não eram conhecidos limites superiores ou inferiores para o tamanho dos autômatos resultantes. Antes deste trabalho, o melhor limite inferior conhecido para o tamanho de um autômato finito não determinístico (AFN) para o fechamento descendente de uma linguagem indexada era duplamente exponencial, e a complexidade de problemas de decisão como inclusão e equivalência de fechamento descendente era conhecida por ser pelo menos co-2-NEXP-difícil.

Metodologia

Os autores resolvem este problema em aberto fornecendo limites superiores e inferiores apertados (assintoticamente correspondentes). Sua abordagem baseia-se em uma abstração algébrica inovadora dos conteúdos da pilha para transformar gramáticas indexadas em gramáticas livres de contexto (GLCs) enquanto preservam o fechamento descendente.

1. Produtividade e Anotação

A construção começa garantindo que a gramática indexada de entrada seja produtiva (toda forma sentencial pode derivar uma palavra terminal). Os autores introduzem uma versão anotada da gramática onde os símbolos da pilha são emparelhados com conjuntos de não-terminais que podem derivar palavras terminais a partir daquela configuração da pilha. Isso previne a geração de termos "mortos" que não podem contribuir para a linguagem, uma propriedade essencial para preservar o fechamento descendente durante as transformações subsequentes.

2. O Monóide da Pilha e Resumos

A inovação técnica central envolve a teoria de semigrupos finitos. Os autores definem um monóide de pilha $M$ (um monóide finito de matrizes booleanas) que codifica o comportamento das operações de pilha (empurrar e pop) em relação aos não-terminais da gramática.

• Resumos: Eles utilizam avanços recentes na teoria de semigrupos (especificamente resultados de Jecker e Gimbert et al.) para calcular resumos de palavras de pilha arbitrariamente longas. Um resumo é uma representação comprimida de uma palavra de pilha que retém informações suficientes para determinar o resultado das operações de empurrar/pop em relação ao monóide $M$.
• Bombeamento e Pulo: Os autores introduzem duas novas regras de derivação, bombear e pular, que permitem a extensão e redução de infixos de pilha que mapeiam para o mesmo elemento idempotente no monóide. Eles provam que essas regras não alteram o fechamento descendente da linguagem.
• Compressão: Ao aplicar essas regras, eles mostram que qualquer conteúdo de pilha pode ser comprimido em um resumo de tamanho limitado (exponencial no tamanho da gramática). Essa compressão efetivamente perde informações sobre o conteúdo exato da pilha, mas preserva o fechamento descendente.

3. Redução para Gramáticas Livres de Contexto

Utilizando esses resumos, os autores constroem uma gramática livre de contexto (GLC) $G_{GLC}$ que simula a gramática indexada original $G$. Em $G_{GLC}$, os conteúdos da pilha da gramática indexada são substituídos por seus resumos.

• Os não-terminais de $G_{GLC}$ são triplos $(A, X, \sigma)$, onde $A$ é um não-terminal, $X$ é um conjunto de não-terminais e $\sigma$ é um resumo viável.
• As operações de empurrar e pop na gramática original são simuladas por operações nos resumos (usando as relações empurrar e pop definidas no monóide).
• Os autores provam que $L(G_{GLC})^\downarrow = L(G)^\downarrow$.

4. Análise de Complexidade

Como o tamanho de um resumo é limitado exponencialmente no tamanho da gramática, a GLC resultante $G_{GLC}$ tem um tamanho duplamente exponencial. Algoritmos existentes para calcular fechamentos descendentes de GLCs produzem um AFN de tamanho exponencial em relação à GLC. Consequentemente, a composição produz um AFN para $L(G)^\downarrow$ de tamanho triplamente exponencial.

Para autômatos finitos determinísticos (AFD), a construção de subconjuntos padrão aplicada ao AFN triplamente exponencial resulta em um limite superior quadruplamente exponencial.

Contribuições e Resultados Chave

Limites Superiores

• Tamanho do AFN: Dada uma gramática indexada de tamanho $n$, um AFN para seu fechamento descendente pode ser computado em tempo triplamente exponencial e tem tamanho de no máximo triplamente exponencial ($O(\exp_3(n))$).
• Tamanho do AFD: Um AFD para o fechamento descendente pode ser construído com tamanho de no máximo quadruplamente exponencial ($O(\exp_4(n))$).
• Problemas de Decisão: Os problemas de inclusão de fechamento descendente ($L_1^\downarrow \subseteq L_2^\downarrow$) e equivalência ($L_1^\downarrow = L_2^\downarrow$) para linguagens indexadas são co-3-NEXP-completos.

Limites Inferiores

Os autores fornecem limites inferiores correspondentes, provando a precisão de seus limites superiores:

• Limite Inferior do AFN: Existe uma família de gramáticas indexadas de tamanho polinomial tal que qualquer AFN para seu fechamento descendente requer pelo menos triplamente exponencial estados. Isso é alcançado construindo uma gramática que gera a linguagem $\{a^{\exp_3(n)}\}$.
• Limite Inferior do AFD: Existe uma família de gramáticas indexadas tal que qualquer AFD para seu fechamento descendente requer pelo menos quadruplamente exponencial estados.
• Limiar de Bombeamento: Os resultados implicam que o limiar de bombeamento para gramáticas indexadas (o comprimento máximo de uma palavra em uma linguagem indexada finita de tamanho $n$) cresce pelo menos triplamente exponencialmente, corrigindo uma afirmação anterior de um limite duplamente exponencial encontrada na literatura.

Significado

O artigo resolve um problema em aberto de longa data regarding a complexidade dos fechamentos descendentes para linguagens indexadas.

1. Limites Apertados: Estabelece que a complexidade é estritamente maior do que para linguagens livres de contexto (que são duplamente exponenciais para AFNs), mas menor do que a torre geral de exponenciais frequentemente associada a sistemas de ordem superior de ordem $k > 2$. O salto de duplamente para triplamente exponencial para linguagens indexadas (ordem-2) é inesperado, dada a crescimento linear da complexidade para outros problemas (como vazio) em relação à ordem do autômato de pilha.
2. Viabilidade Algorítmica: Confirma que uma construção primitivo-recursiva existe, resolvendo a questão de se o problema é meramente computável ou efetivamente construtível dentro de uma classe de complexidade específica.
3. Avance Metodológico: A técnica de usar resumos baseados em semigrupos para comprimir conteúdos de pilha enquanto preserva fechamentos descendentes oferece uma nova ferramenta para analisar sistemas de ordem superior, potencialmente aplicável a classes mais amplas de sistemas de estado infinito.

Os autores enfatizam que seus resultados são derivados de uma transformação construtiva de gramáticas indexadas para GLCs, aproveitando as propriedades algébricas do monóide de pilha para gerenciar a natureza ilimitada das pilhas de uma maneira que preserva a estrutura de subpalavras essencial para fechamentos descendentes.