Riepilogo Tecnico: Sulla Complessità del Problema di Corrispondenza delle Espressioni Regular con Backreference

1. Definizione del Problema e Motivazione

Il documento esamina la complessità computazionale fine-granulare del problema di corrispondenza delle Espressioni Regular con Backreference (REWB). Mentre le espressioni regular (Regex) classiche possono essere corrette in tempo lineare rispetto alla lunghezza della stringa di input $|w|$ utilizzando la costruzione di Thompson, i motori pratici supportano i backreference (ad esempio, (E)x per catturare una sottostringa e \x per riutilizzarla). Questa funzionalità estende rigorosamente il potere espressivo delle Regex (permettendo il riconoscimento di linguaggi non regolari come $\{ww \mid w \in \Sigma^*\}$) ma introduce rischi algoritmici significativi.

La motivazione deriva dagli attacchi di Denial of Service tramite Espressioni Regular (ReDoS), in cui gli avversari elaborano input per innescare comportamenti nel caso peggiore nei motori di corrispondenza. Incidenti degni di nota su Stack Overflow (2016) e Cloudflare (2019) hanno dimostrato che anche un comportamento quadratico ($O(|w|^2)$) nei motori basati sul backtracking può causare interruzioni catastrofiche del servizio. Gli autori pongono la domanda fondamentale: È possibile costruire motori sicuri contro ReDoS per REWB che operino in tempo lineare o quasi-lineare?

Il documento si concentra sulle $r$-use $k$-REWB, definite come espressioni con $k$ variabili distinte dove il numero totale di esecuzioni di backreference in qualsiasi calcolo è limitato da $r$.

2. Metodologia e Approccio Tecnico

Il documento adotta un approccio duale: stabilire limiti inferiori condizionali (durezza) e progettare algoritmi efficienti per sottoclassi specifiche.

2.1 Risultati di Durezza

Gli autori rafforzano i precedenti risultati di complessità riducendo problemi noti per essere difficili alla corrispondenza REWB:

• Durezza W[2]: Riducendo il problema del $k$-Dominating Set, dimostrano che la corrispondenza REWB è W[2]-difficile quando parametrizzata dalla dimensione dell'espressione $|E|$. Questo rafforza il noto risultato di durezza W[1].
• Limiti Inferiori Condizionali (Rilevamento dei Triangoli): Assumendo l'"Ipotesi di Non-Tempo-Quasi-Lineare" per il Rilevamento dei Triangoli, mostrano che anche il problema altamente ristretto 2-use 2-REWB non può essere risolto in tempo $O(|w|^{1+\delta})$ per alcun $\delta > 0$.
• Limiti Inferiori Condizionali (k-OV): Sotto l'ipotesi $k$-Orthogonal Vectors (k-OV) (più debole di SETH), dimostrano che la corrispondenza $k$-REWB non può essere risolta in tempo $O(|w|^{2k-\epsilon})$. Ciò implica che per $k$ generale, il tempo quasi-lineare è improbabile.

2.2 Risultati Algoritmici

Il contributo algoritmico principale si concentra sulle 1-use REWB (espressioni con una variabile referenziata esattamente una volta).

• Trasformazione in Forma Canonica: Gli autori dimostrano che qualsiasi 1-use REWB può essere trasformata in una forma canonica che coinvolge una somma di termini come $A (B)_x C \backslash x D$, dove $A, B, C, D$ sono Regex classiche. Questo è denominato il problema ABCBD.
• Strategia di Decomposizione: Il problema ABCBD è decomposto in due sottoproblemi:
  1. Problema XYYZ: Il caso in cui le due occorrenze di $B$ sono adiacenti ($w = w_A w_B w_B w_D$). Questo è risolto utilizzando l'enumerazione della potenza locale massima di Crochemore e le proprietà degli insiemi infine periodici derivati dai monoidi di transizione.
  2. Problema ABCBD Ramificato: Il caso in cui le due occorrenze di $B$ sono separate da una $C$ non vuota, e i caratteri immediatamente successivi alle due occorrenze di $B$ differiscono.
• Albero dei Suffix e Decomposizione Pesante-Leggera: Per il caso Ramificato, l'algoritmo utilizza l'albero dei suffix della stringa di input $w$. Impiega la decomposizione pesante-leggera per partizionare lo spazio di ricerca.
• Strutture Dati:
  • Foreste di Fattorizzazione: Utilizzate per valutare l'appartenenza alla Regex su sottostringhe in tempo costante dopo un pre-processing lineare.
  • Monoidi di Transizione: Sfruttati per tracciare lo stato delle Regex $A, B, C, D$ in modo efficiente.
  • Enumeratori Personalizzati: Gli autori progettano strutture dati specializzate (RightEnumerator, LeftEnumerator, AuxiliaryEnumerator) per gestire l'enumerazione delle transizioni. Queste strutture utilizzano aggiornamenti lazy e strategie di unione di insiemi disgiunti (DSU) per gestire vincoli che variano con la lunghezza della sottostringa $w_B$.

3. Risultati Chiave

Durezza

• Teorema 3: La corrispondenza REWB è W[2]-difficile parametrizzata dalla dimensione dell'espressione.
• Teorema 4: Assumendo l'ipotesi del Rilevamento dei Triangoli, la corrispondenza 2-use 2-REWB richiede tempo super-lineare (specificamente, non $O(|w|^{1+\delta})$).
• Teorema 5: Sotto l'ipotesi $k$-OV, la corrispondenza $k$-REWB richiede tempo $\Omega(|w|^{2k-\epsilon})$.

Algoritmi

• Teorema 7 (Risultato Principale): Il problema ABCBD ammette un algoritmo di tempo $O(|w| \log^2 |w|)$. La costante nascosta dipende esponenzialmente dalle dimensioni delle Regex $A, B, C, D$ ($2^{O((|A|+|B|+|C|+|D|)^2)}$).
• Teorema 8: Di conseguenza, il problema di corrispondenza 1-use REWB ammette un algoritmo di tempo $O(|w| \log^2 |w|)$.
• Teorema 9: Il problema XY$\alpha$Z (che generalizza XYYZ a $\alpha$ ripetizioni) ammette un algoritmo di tempo $O(|w| \log |w|)$.

Questi risultati rappresentano un miglioramento significativo rispetto al precedente miglior algoritmo noto $O(|w|^2)$ per il problema ABCBD di Nogami e Terauchi (MFCS 2025).

4. Significato e Affermazioni

Il documento afferma di fornire una comprensione fondamentale del panorama della complessità per la corrispondenza REWB:

1. Sicurezza ReDoS: Stabilisce che, sebbene la corrispondenza REWB generale sia probabilmente intrattabile per tempi quasi-lineari, una sottoclasse praticamente rilevante (1-use REWB) può essere corretta in tempo quasi-lineare. Ciò suggerisce che i motori che supportano backreference 1-use potrebbero teoricamente essere resi sicuri contro ReDoS.
2. Complessità Fine-Granulare: Il lavoro delimita il confine tra casi trattabili e intrattabili. Dimostra che aumentare il numero di utilizzi di backreference da 1 a 2 (anche con sole 2 variabili) spinge probabilmente il problema fuori dal regime quasi-lineare.
3. Innovazione Algoritmica: Il documento introduce un quadro algoritmico complesso ma altamente non banale che combina alberi dei suffix, foreste di fattorizzazione e monoidi di transizione per risolvere un problema precedentemente ritenuto richiedere tempo quadratico.

Gli autori dichiarano esplicitamente che il loro algoritmo è uniforme, il che significa che elabora l'espressione e la stringa di input insieme senza consigli non uniformi dipendenti dall'espressione fissa. Riconoscono che la dipendenza esponenziale dalla dimensione dell'espressione $|E|$ rimane una limitazione per espressioni molto grandi, e lasciano aperta la questione se esista un algoritmo di tempo strettamente lineare ($O(|w|)$) o se i fattori logaritmici possano essere rimossi.

5. Limitazioni e Problemi Aperti

Il documento identifica diverse direzioni aperte:

• Complessità di $r$-use 1-REWB: La complessità per $r$-use 1-REWB dove $r \ge 2$ rimane aperta.
• Tempo Lineare: Se il limite $O(|w| \log^2 |w|)$ possa essere migliorato a $O(|w|)$.
• Dipendenza dall'Espressione: Ridurre la dipendenza esponenziale da $|E|$ a polinomiale mantenendo una dipendenza quasi-lineare da $|w|$.
• Funzionalità più Ampie: Estendere questi risultati ad altre funzionalità pratiche delle regex come lookaround, grouping atomico e stelle greedy/lazy.