Riepilogo Tecnico: La Complessità delle Chiusure Discendenti dei Linguaggi Indicizzati

Enunciato del Problema

Il lavoro affronta la complessità computazionale della costruzione delle chiusure discendenti per i linguaggi indicizzati. La chiusura discendente di un linguaggio $L$, indicata con $L^\downarrow$, è l'insieme di tutti i sotto-parole sparsi delle parole in $L$. Per il Lemma di Higman, $L^\downarrow$ è sempre un linguaggio regolare, rendendola una sovrapprossimazione regolare cruciale utilizzata nella verifica di sistemi a stati infiniti (ad esempio, model checking di ordine superiore, programmi asincroni e sistemi di canali perdenti).

Sebbene la calcolabilità delle chiusure discendenti per i linguaggi indicizzati (equivalenti agli automi a pila di ordine-2 o 2-PDA) fosse stata stabilita nel 2015 tramite un algoritmo generale basato su quasi-buoni ordinamenti, i limiti di complessità per questa costruzione rimanevano un problema aperto. Nello specifico, non era noto se esistesse una costruzione primitivo-ricorsiva e non erano noti limiti superiori o inferiori sulla dimensione degli automi risultanti. Prima di questo lavoro, il miglior limite inferiore noto per la dimensione di un automa finito non deterministico (NFA) per la chiusura discendente di un linguaggio indicizzato era doppiamente esponenziale, e la complessità dei problemi decisionali come l'inclusione e l'equivalenza delle chiusure discendenti era nota per essere almeno co-2-NEXP-dura.

Metodologia

Gli autori risolvono questo problema aperto fornendo limiti superiori e inferiori stretti (asintoticamente coincidenti). Il loro approccio si basa su una nuova astrazione algebrica dei contenuti dello stack per trasformare le grammatiche indicizzate in grammatiche libere dal contesto (CFG) preservando la chiusura discendente.

1. Produttività e Annotazione

La costruzione inizia assicurandosi che la grammatica indicizzata di input sia produttiva (ogni forma sentenziale può derivare una parola terminale). Gli autori introducono una versione annotata della grammatica in cui i simboli dello stack sono accoppiati con insiemi di non-terminali che possono derivare parole terminali da quella configurazione dello stack. Questo previene la generazione di termini "morti" che non possono contribuire al linguaggio, una proprietà essenziale per preservare la chiusura discendente durante le successive trasformazioni.

2. Il Monoide dello Stack e i Riassunti

L'innovazione tecnica centrale coinvolge la teoria dei semigruppi finiti. Gli autori definiscono un monoide dello stack $M$ (un monoide finito di matrici booleane) che codifica il comportamento delle operazioni sullo stack (spinta e pop) rispetto ai non-terminali della grammatica.

• Riassunti: Sfruttano recenti progressi nella teoria dei semigruppi (in particolare i risultati di Jecker e Gimbert et al.) per calcolare i riassunti di parole dello stack di lunghezza arbitraria. Un riassunto è una rappresentazione compressa di una parola dello stack che mantiene informazioni sufficienti per determinare l'esito delle operazioni di spinta/pop rispetto al monoide $M$.
• Pumping e Skipping: Gli autori introducono due nuove regole di derivazione, pump e skip, che permettono l'estensione e la riduzione di infissi dello stack che mappano allo stesso elemento idempotente nel monoide. Dimostrano che queste regole non alterano la chiusura discendente del linguaggio.
• Compressione: Applicando queste regole, mostrano che qualsiasi contenuto dello stack può essere compresso in un riassunto di dimensione limitata (esponenziale rispetto alla dimensione della grammatica). Questa compressione perde efficacemente informazioni sul contenuto esatto dello stack ma preserva la chiusura discendente.

3. Riduzione alle Grammatiche Libere dal Contesto

Utilizzando questi riassunti, gli autori costruiscono una grammatica libera dal contesto (CFG) $G_{CFG}$ che simula la grammatica indicizzata originale $G$. In $G_{CFG}$, i contenuti dello stack della grammatica indicizzata sono sostituiti dai loro riassunti.

• I non-terminali di $G_{CFG}$ sono triple $(A, X, \sigma)$, dove $A$ è un non-terminale, $X$ è un insieme di non-terminali e $\sigma$ è un riassunto fattibile.
• Le operazioni di spinta e pop nella grammatica originale sono simulate da operazioni sui riassunti (utilizzando le relazioni push e pop definite sul monoide).
• Gli autori dimostrano che $L(G_{CFG})^\downarrow = L(G)^\downarrow$.

4. Analisi della Complessità

Poiché la dimensione di un riassunto è limitata esponenzialmente rispetto alla dimensione della grammatica, la CFG risultante $G_{CFG}$ ha una dimensione doppiamente esponenziale. Gli algoritmi esistenti per il calcolo delle chiusure discendenti delle CFG producono un NFA di dimensione esponenziale rispetto alla CFG. Di conseguenza, la composizione produce un NFA per $L(G)^\downarrow$ di dimensione triplemente esponenziale.

Per gli automi finiti deterministici (DFA), la costruzione standard degli insiemi applicata all'NFA triplamente esponenziale risulta in un limite superiore quadruplamente esponenziale.

Contributi e Risultati Chiave

Limiti Superiori

• Dimensione NFA: Data una grammatica indicizzata di dimensione $n$, un NFA per la sua chiusura discendente può essere calcolato in tempo triplemente esponenziale e ha dimensione al massimo triplemente esponenziale ($O(\exp_3(n))$).
• Dimensione DFA: Un DFA per la chiusura discendente può essere costruito con dimensione al massimo quadruplamente esponenziale ($O(\exp_4(n))$).
• Problemi Decisionali: I problemi di inclusione delle chiusure discendenti ($L_1^\downarrow \subseteq L_2^\downarrow$) e di equivalenza ($L_1^\downarrow = L_2^\downarrow$) per i linguaggi indicizzati sono co-3-NEXP-completi.

Limiti Inferiori

Gli autori forniscono limiti inferiori coincidenti, dimostrando la strettezza dei loro limiti superiori:

• Limite Inferiore NFA: Esiste una famiglia di grammatiche indicizzate di dimensione polinomiale tale che qualsiasi NFA per la loro chiusura discendente richiede almeno stati triplemente esponenziali. Ciò è ottenuto costruendo una grammatica che genera il linguaggio $\{a^{\exp_3(n)}\}$.
• Limite Inferiore DFA: Esiste una famiglia di grammatiche indicizzate tale che qualsiasi DFA per la loro chiusura discendente richiede almeno stati quadruplamente esponenziali.
• Soglia di Pumping: I risultati implicano che la soglia di pumping per le grammatiche indicizzate (la lunghezza massima di una parola in un linguaggio indicizzato finito di dimensione $n$) cresce almeno triplamente esponenzialmente, correggendo un precedente affermazione di un limite doppiamente esponenziale presente in letteratura.

Significato

Il lavoro risolve un problema aperto di lunga data riguardante la complessità delle chiusure discendenti per i linguaggi indicizzati.

1. Limiti Stretti: Stabilisce che la complessità è strettamente superiore a quella dei linguaggi liberi dal contesto (che sono doppiamente esponenziali per gli NFA) ma inferiore alla torre generale di esponenziali spesso associata ai sistemi di ordine $k > 2$. Il salto da doppiamente a triplamente esponenziale per i linguaggi indicizzati (ordine-2) è inaspettato data la crescita lineare della complessità per altri problemi (come il vuoto) rispetto all'ordine dell'automa a pila.
2. Fattibilità Algoritmica: Conferma che esiste una costruzione primitivo-ricorsiva, risolvendo la questione se il problema sia meramente calcolabile o costruttibile efficacemente all'interno di una specifica classe di complessità.
3. Avanzamento Metodologico: La tecnica di utilizzare riassunti basati sui semigruppi per comprimere i contenuti dello stack preservando le chiusure discendenti offre un nuovo strumento per l'analisi di sistemi di ordine superiore, potenzialmente applicabile a classi più ampie di sistemi a stati infiniti.

Gli autori sottolineano che i loro risultati sono derivati da una trasformazione costruttiva delle grammatiche indicizzate in CFG, sfruttando le proprietà algebriche del monoide dello stack per gestire la natura illimitata degli stack in un modo che preserva la struttura delle sotto-parole essenziale per le chiusure discendenti.