Compiling Rewrite Rules to Finite-State Transducers with the Worsening Trick

Sintesi Tecnica: Compilazione di Regole di Riscrittura in Trasduttori a Stati Finiti con il Trucco del Peggioramento (Worsening Trick)

Enunciato del Problema
I trasduttori a stati finiti (FST) sono fondamentali per modellare la riscrittura di stringhe nella linguistica computazionale, in particolare per le regole fonologiche e morfologiche della forma $A \to B / L \_ R$. Qui, stringhe da un linguaggio regolare $A$ vengono sostituite da $B$ all'interno del contesto dei linguaggi regolari $L$ e $R$. Compilare tali regole generali in FST è computazionalmente complesso a causa delle sovrapposizioni di corrispondenze (matches), dei molteplici contesti e della necessità di gestire varie preferenze (ad esempio, corrispondenze a sinistra, più lunghe o più brevi). I metodi di compilazione tradizionali, come quelli di Kaplan e Kay o Karttunen, si basano su composizioni intricate che coinvolgono marcatori ausiliari per vincolare i siti di riscrittura. Questi approcci risultano spesso in formule complesse e non uniformi, difficili da estendere ad elementi avanzati come la riscrittura parallela, le trasduzioni arbitrarie o le regole pesate.

Metodologia
Gli autori propongono uno schema di compilazione basato sul "trucco del peggioramento" (worsening trick), una strategia precedentemente applicata a insiemi regolari e trasduzioni. Il metodo opera in tre stadi trasparenti per compilare una regola $A \to B / L \_ R$:

1. Generazione dei Candidati ($T_{base}$): Il sistema genera tutti i possibili candidati di riscrittura tramite la bracketing (inserimento di parentesi) dei potenziali siti di trasduzione. Ciò viene ottenuto costruendo un trasduttore base che permette ai simboli dell'alfabeto di input $\Sigma$ di passare inalterati o di essere sostituiti da stringhe appartenenti a $B$ all'interno di parentesi $< \dots >$ che rappresentano la trasduzione $A:B$. I confini delle parole sono esplicitamente marcati con # per trattare i contesti di bordo in modo uniforme.
2. Restrizione del Contesto ($L_{context}$): I candidati che contengono siti di riscrittura in contesti illeciti vengono filtrati. Invece di utilizzare formule esponenziali per i molteplici contesti, gli autori impiegano una tecnica di "posizione punteggiata" (Yli-Järä e Koskenniemi). Un simbolo ausiliario · viene utilizzato per marcare un singolo sito di riscrittura, e un linguaggio $K$ viene costruito per rappresentare stringhe in cui questa posizione marcata è circondata da contesti validi ($L$ e $R$). L'intersezione tra i contesti validi e l'insieme dei candidati produce l'insieme delle riscritture legali e opzionali.
3. Filtraggio delle Preferenze (Peggioramento): Per imporre la riscrittura obbligatoria e specifiche preferenze (ad esempio, la più a sinistra, la più lunga o la più breve), il sistema definisce un trasduttore di "peggioramento" ($W$). Questo trasduttore mappa un candidato "migliore" in uno "peggiore" rimuovendo o spostando le parentesi di riscrittura (ad esempio, annullando una riscrittura o accorciando un intervallo). Il trasduttore finale è costruito filtrando ogni candidato che può essere reso strettamente peggiore applicando $W$. Matematicamente, per un insieme di candidati $C$ e un peggioratore $W$, l'insieme ottimale è $C \cap \neg \text{range}(C \circ W)$.

Questo framework è implementato in PyFoma e supporta:

• Molteplici Contesti: Gestiti tramite unione nel linguaggio della posizione punteggiata.
• Riscrittura Diretta: Le preferenze come la più a sinistra, la più lunga o la più breve sono codificate da specifici trasduttori di peggioramento ($W_{left}$, $W_{long}$, $W_{short}$).
• Trasduzioni Arbitrarie: L'input $T$ non deve essere un semplice prodotto cartesiano; può essere qualsiasi FST.
• Riscrittura Parallela: Molte regole sono gestite tramite parentesi indicizzate, con restrizione del contesto e peggioramento applicati per indice.
• Pesi: La costruzione opera all'interno del semiring tropicale, poiché i peggioratori filtrano i candidati senza alterarne i pesi assegnati.
• Gestione di Epsilon: Un filtro specifico impedisce la presenza di coppie di parentesi vuote consecutive per limitare le inserzioni di epsilon a singoli siti per ogni confine.

Contributi Chiave

• Uniformità e Compattezza: Il documento presenta una formulazione in cui la logica di compilazione è espressa con formule sostanzialmente più brevi e uniformi rispetto agli approcci classici ricchi di marcatori o a multi-nastro.
• Estendibilità: La costruzione si estende naturalmente a modalità complesse (regole parallele, pesi, markup, controllo del contesto sul lato output) senza richiedere nuovi tipi di regole o macchinari ausiliari.
• Implementazione e Validazione: Gli autori hanno implementato il compilatore in PyFoma. La validazione è stata eseguita contro l'established compilatore foma basato su C, utilizzando una collezione di 31 grammatiche (427 regole) e una suite di regressione automatizzata di 2.217 casi.
• Equivalenza: In tutti i casi testati in cui la semantica coincide, i trasduttori risultanti sono strutturalmente identici a quelli prodotti da foma (differendo solo per la numerazione degli stati), confermando la correttezza dell'approccio basato sul peggioramento.

Significato e Rivendicazioni
Il documento sostiene che il trucco del peggioramento fornisca un'alternativa robusta e algebrica alle attività procedurali di selezione nella fonologia a stati finiti. Generando un insieme regolare di candidati e filtrandoli tramite una relazione di peggioramento, è possibile codificare ordini di preferenza complessi in modo dichiarativo all'interno del calcolo regolare. Gli autori affermano che questo approccio non solo riproduce la semantica stabilita dai compilatori classici, ma semplifica anche l'estensione teorica e pratica dei sistemi di riscrittura. La tecnica è presentata non solo come uno strumento di compilazione, ma come un modello generale di progettazione a stati finiti per estrarre sottoinsiemi preferiti di linguaggi e relazioni regolari (ad esempio, rappresentanti minimi o massimi). Il lavoro rafforza l'utilità del trucco del peggioramento oltre le sue precedenti applicazioni nella Teoria dell'Ottimalità a stati finiti, dimostrando la sua efficacia nel gestire l'intero spettro delle classiche modalità di regole di riscrittura.