💻 computer science

Kofola 1.0: A Modular Approach to {\omega}-Regular Complementation and Inclusion Checking (Technical Report)

Questo articolo introduce Kofola, uno strumento efficiente e robusto che impiega un framework modulare per decomporre gli automi di Büchi in componenti fortemente connesse per la verifica di complementazione e inclusione su misura, dimostrando prestazioni superiori rispetto agli strumenti all'avanguardia grazie alla verifica di vuoto on-the-fly e a nuove euristiche.

Autori originali: Ondrej Alexaj, Vojtěch Havlena, Lukáš Holík, Ondřej Lengál, Yong Li, Nicolas Mazzocchi

Pubblicato 2026-05-18

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Ondrej Alexaj, Vojtěch Havlena, Lukáš Holík, Ondřej Lengál, Yong Li, Nicolas Mazzocchi

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di essere un ispettore di controllo qualità per una fabbrica massiccia e infinita. Questa fabbrica produce flussi infiniti di prodotti (chiamati "parole" nell'informatica). Hai due macchine: Macchina A e Macchina B.

Il tuo lavoro è rispondere a una domanda molto difficile: "Ogni singolo prodotto che la Macchina A produce, viene prodotto anche dalla Macchina B?"

Se la risposta è "Sì", allora la Macchina A è sicura da usare. Se esiste anche un solo prodotto che la Macchina A produce e che la Macchina B non produce mai, allora la Macchina A è insicura.

Questo è il problema centrale del Controllo di Inclusione dei Linguaggi. È un compito fondamentale per verificare che software e hardware informatici si comportino correttamente. Tuttavia, poiché i flussi di prodotti sono infiniti, controllarlo manualmente è impossibile. Hai bisogno di un robot super-intelligente per farlo.

Ecco Kofola, un nuovo robot altamente efficiente progettato per risolvere questo problema. Ecco come funziona, scomposto in concetti semplici:

1. Il Vecchio Metodo vs. Il Metodo Kofola

In precedenza, i robot che tentavano di risolvere questo problema dovevano osservare l'intero pavimento della fabbrica contemporaneamente. Cercavano di costruire una mappa gigante di ogni possibile percorso che la Macchina A poteva intraprendere e confrontarla con la Macchina B. Questa mappa era così enorme che spesso faceva esplodere il cervello del robot (un problema chiamato "esplosione dello spazio degli stati").

Il Segreto di Kofola: L'Approccio Modulare
Invece di guardare l'intera fabbrica tutta insieme, Kofola è un maestro organizzatore. Guarda la Macchina B e dice: "Questa fabbrica non è un unico grande caos; è in realtà composta da quartieri distinti."

Kofola scompone la Macchina B in Componenti Fortemente Connessi (CFC). Pensa a questi come a diverse stanze o zone della fabbrica:

I Vicoli Ciechi: Stanze dove la macchina smette di produrre prodotti.
I Semplici Cicli: Stanze dove la macchina gira in tondo facendo la stessa cosa all'infinito.
Le Zone Deterministiche: Stanze dove la macchina ha una sola scelta ad ogni passo (come un treno su un binario singolo).
Le Zone Caotiche: Stanze dove la macchina ha molte scelte e può andare in direzioni diverse (come un labirinto).

Kofola tratta ogni "quartiere" in modo diverso. Usa uno strumento specializzato e semplice per i cicli semplici e uno strumento pesante per le zone caotiche. Non spreca energia cercando di risolvere le parti facili con un martello pneumatico.

2. La Nuova Scoperta "IADAC"

Il documento introduce un nuovo tipo di quartiere chiamato IADAC (Componente Accettante Quasi Deterministico Iniziale).

L'Analogia: Immagina un corridoio che porta in una stanza. Il corridoio è una pista dritta a una sola corsia (deterministica). Una volta entrata nella stanza, potresti avere delle scelte. Ma ecco il trucco: una volta uscita da quella stanza, non puoi più tornare al corridoio.
Perché è importante: Poiché il corridoio è così prevedibile, Kofola può usare un metodo molto veloce e leggero per controllarlo, invece del metodo pesante e lento necessario per le parti caotiche. Questo è un nuovo tipo di zona che gli autori hanno identificato e ottimizzato.

3. L'Ispettore "Pigro" (Controllo in Tempo Reale)

Di solito, per verificare se la fabbrica è sicura, devi costruire l'intera mappa della fabbrica prima di poter dire "Sicura" o "Insicura".

Kofola è massimamente pigro (in senso positivo). Inizia a costruire la mappa, ma non appena trova prove sufficienti per decidere la risposta, si ferma.

Se trova un "prodotto cattivo" presto, grida immediatamente: "Insicura!" e smette di lavorare.
Non spreca tempo a mappare il resto della fabbrica se la risposta è già chiara.

Questo viene fatto utilizzando un nuovo algoritmo di "controllo di vuoto". Immagina di cercare un tipo specifico di bug in una stanza buia. Invece di accendere le luci per l'intera stanza, accendi la tua torcia solo sul percorso che stai percorrendo. Se trovi il bug, ti fermi. Se percorri tutto il sentiero e non lo trovi, sai che la stanza è libera. Kofola fa questo istantaneamente mentre costruisce la mappa.

4. I Risultati: Kofola Vince la Gara

Gli autori hanno testato Kofola contro i migliori robot esistenti (strumenti come Spot, Rabit e Bait) utilizzando migliaia di progetti reali di fabbrica.

Robustezza: Kofola è stato l'unico strumento che ha risolto con successo ogni singolo caso di test senza crashare o rimanere senza memoria. Gli altri hanno fallito in molti casi difficili.
Velocità: Su molti problemi pratici, Kofola non era solo più veloce; era ordini di grandezza più veloce. In alcuni casi, mentre altri strumenti stavano ancora cercando di costruire la mappa dopo 2 minuti, Kofola aveva già finito in una frazione di secondo.
Dimensione: Le mappe costruite da Kofola erano spesso molto più piccole e compatte di quelle costruite dai concorrenti.

Riepilogo

Kofola è un nuovo strumento super-efficiente per verificare se un sistema informatico è "contenuto" all'interno di un altro. Funziona così:

Scomponendo il problema in quartieri più piccoli e gestibili.
Usando lo strumento giusto per ogni tipo specifico di quartiere (incluso un nuovo tipo che ha scoperto).
Essendo pigro, fermando il lavoro nel momento in cui ha informazioni sufficienti per dare una risposta.

Il risultato è uno strumento più veloce, più affidabile e in grado di gestire problemi molto più grandi e complessi di qualsiasi altro attualmente disponibile. È un significativo aggiornamento per il "controllo qualità" dei sistemi informatici.

Riepilogo Tecnico: Kofola 1.0 – Un Approccio Modulare alla Complementazione e al Controllo di Inclusione ω-Regolari

Enunciato del Problema

Il controllo dell'inclusione linguistica per automi di Büchi (BA) è un problema fondamentale nella verifica basata sulla teoria degli automi, con applicazioni critiche nel model checking, nel monitoraggio e nella dimostrazione di teoremi. Il problema è completo per PSpace e rimane computazionalmente oneroso man mano che le specifiche del sistema crescono in dimensione e complessità. Decidere se $L_1 \subseteq L_2$ si riduce al controllo della vacuità di $L_1 \cap \overline{L_2}$ , dove $\overline{L_2}$ è il complemento di $L_2$ . Questa riduzione presenta due sfide principali:

Complementazione Compatta: Costruire l'automa complementare $\overline{L_2}$ in modo efficiente senza causare un'esplosione dello spazio degli stati.
Esplorazione Efficiente: Esplorare l'automa prodotto di $L_1 \cap \overline{L_2}$ , che è spesso enorme.

Gli strumenti esistenti fanno largamente affidamento su costruzioni di complementazione basate su Ramsey o sulla determinizzazione di tipo classico, risalenti a oltre tre decenni fa. Sebbene esistano recenti avanzamenti nella complementazione, questi non sono stati integrati completamente nei controllori di inclusione pratici.

Metodologia

Il documento presenta Kofola, uno strumento efficiente implementato in C++ che realizza un framework modulare di complementazione all'avanguardia. La metodologia si basa sulla decomposizione dell'automa in ingresso in componenti fortemente connesse (SCC) e sull'applicazione di algoritmi di complementazione adattati a ciascun componente in base alle sue proprietà strutturali.

1. Decomposizione Strutturale e Classificazione dei Componenti

Kofola esegue un'analisi strutturale fine-granulare dell'automa da complementare ( $A_2$ ). Classifica le sue massimali SCC in quattro categorie distinte:

Componenti non accettanti: Gestite tramite la costruzione classica degli insiemi.
Componenti Accettanti Intrinsecamente Deboli (IWACs): Componenti in cui tutti i cicli accettano.
Componenti Accettanti Deterministiche (DACs): Componenti con sole transizioni deterministiche.
Componenti Accettanti Inizialmente Quasi-Deterministiche (IADACs): Un nuovo tipo di componente identificato in questo documento. Si tratta di SCC deterministiche raggiungibili dagli stati iniziali tramite SCC deterministiche, permettendo la non-deterministicità solo sui percorsi privi di cicli tra le SCC.
Componenti Accettanti Non-Deterministiche (NACs): Le restanti SCC accettanti.

2. Framework Modulare di Complementazione

Per ogni tipo di componente, Kofola applica un algoritmo parziale di complementazione dedicato:

IWACs: Utilizza la costruzione classica di Miyano-Hayashi, generando una condizione di accettazione $Inf(1)$.
DACs: Utilizza una modifica dell'algoritmo NCSB, generando una condizione di accettazione $Inf(2)$.
NACs: Supporta due approcci in base al compito:
- Complementazione: Utilizza un approccio basato sulla determinizzazione (variante di Safra-Piterman) per produrre automi più piccoli.
- Controllo di Inclusione: Utilizza un approccio basato sulle fette (slice-based), più adatto al test di vacuità del prodotto on-the-fly.
IADACs: Il documento introduce un nuovo algoritmo parziale per queste componenti. Determinizza le IADACs mediante una costruzione degli insiemi ed emette un marchio di rifiuto ($Fin(0)$) ogni volta che un percorso tracciato vede una transizione accettante. La correttezza si basa sul fatto che i percorsi nelle IADACs sono limitati a causa della loro non-deterministicità ristretta.

L'algoritmo di livello superiore sincronizza queste costruzioni parziali. L'automa complementare risultante è un Automa di Rabin Generalizzato Semplice (SGRA) con una singola condizione di accettazione della forma $Fin(0) \land Inf(1) \land \dots \land Inf(k-1)$ .

3. Controllo di Vacuità On-the-Fly

Per affrontare l'esplosione dello spazio degli stati nel controllo di inclusione, Kofola impiega un nuovo algoritmo di controllo di vacuità on-the-fly per il risultante SGRA.

Costruzione Pigra: A differenza degli strumenti che richiedono la costruzione esplicita dell'intero automa prodotto, Kofola esplora lo spazio degli stati in modo pigro.
Algoritmo: L'algoritmo è una variante dell'algoritmo di Couvreur estesa con un predicato $Fin$. Esegue una ricerca in profondità, gestendo uno stack di insiemi di transizioni per rilevare le SCC.
Terminazione: La ricerca termina non appena lo spazio degli stati esplorato è sufficiente per decidere il risultato (trovando un ciclo accettante o dimostrando la vacuità). Questo minimizza la parte generata del complemento, il che è cruciale poiché la complementazione è la principale fonte di esplosione.

Contributi Chiave

Strumento Kofola: Uno strumento efficiente e modulare per la complementazione BA e il controllo di inclusione linguistica.
Identificazione delle IADACs: L'introduzione e la formalizzazione delle Componenti Accettanti Inizialmente Quasi-Deterministiche (IADACs) come una classe strutturale distinta.
Nuovo Algoritmo di Complementazione: Un algoritmo parziale dedicato per le IADACs che genera la condizione $Fin(0)$, consentendo la costruzione di una singola coppia di Rabin generalizzata.
Controllo di Vacuità Pigro: Un nuovo algoritmo on-the-fly per gli SGRA che evita la costruzione esplicita dell'intero automa, permettendo una terminazione anticipata.
Framework Modulare: Un'architettura flessibile che permette la combinazione sincrona di diversi algoritmi parziali basata sull'analisi strutturale.

Risultati Sperimentali

Gli autori hanno valutato Kofola contro strumenti all'avanguardia: Spot, Ranker, Owl, Bait, Forklift e Rabit.

Benchmark di Complementazione

Dataset: 31.273 automi da fonti diverse (terminazione di programmi, logica delle parole di Sturmian, iperproprietà, S1S, traduzione LTL e generazione casuale).
Robustezza: Kofola è stato l'unico strumento a complementare con successo tutti i 31.273 automi in ingresso. Lo strumento successivo più robusto, Spot, ha fallito su 2 istanze a causa di limiti di memoria.
Dimensione: Kofola ha prodotto automi complementari significativamente più piccoli in media (79,24 stati) rispetto a Spot (115,38 stati) e Ranker (45,80 stati, sebbene Ranker abbia fallito su 443 istanze).
Prestazioni: Kofola ha risolto il maggior numero di istanze e spesso ha superato i concorrenti di diversi ordini di grandezza nel tempo di esecuzione.

Benchmark di Controllo di Inclusione

Dataset: 1.014 problemi di inclusione da terminazione di programmi, verifica di sistemi concorrenti, model checking di iperproprietà e dimostrazione di teoremi.
Prestazioni: Kofola ha risolto il maggior numero di istanze (solo 2 irrisolte) e ha avuto il tempo di esecuzione totale più basso (141 secondi per i problemi risolti).
Confronto: Kofola ha vinto nettamente contro Spot(Det) su 263 istanze e ha perso su sole 0. Ha superato significativamente gli strumenti basati su Ramsey (Bait, Forklift, Rabit), che spesso richiedevano un ordine di grandezza in più di tempo.
Osservazione: Il 98% degli automi sul lato destro delle query di inclusione (quelli da complementare) erano automi ascensore (contenenti nessuna NAC), evidenziando la rilevanza pratica dello sfruttamento delle proprietà strutturali.

Significato e Affermazioni

Il documento afferma che Kofola stabilisce un nuovo standard per efficienza e robustezza nella complementazione BA e nel controllo di inclusione. Il suo significato risiede in:

Praticità: Porta tecniche moderne di complementazione basate sulla decomposizione al controllo di inclusione pratico, superando le costruzioni classiche.
Scalabilità: Combinando la decomposizione strutturale con il controllo di vacuità pigro on-the-fly, mitiga efficacemente l'esplosione dello spazio degli stati, risolvendo istanze intrattabili per gli strumenti esistenti.
Estendibilità: L'architettura modulare permette l'integrazione di nuovi algoritmi di complementazione parziale per specifici tipi di componenti.

Gli autori posizionano Kofola non semplicemente come un miglioramento incrementale, ma come uno strumento altamente competitivo che spesso supera le soluzioni all'avanguardia di diversi ordini di grandezza su benchmark derivati da applicazioni pratiche.