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

Resumo Técnico: Compilação de Regras de Reescrita para Transdutores de Estados Finitos com o Truque do Pioramento (Worsening Trick)

Enunciado do Problema
Transdutores de estados finitos (FSTs) são fundamentais para modelar a reescrita de cadeias na linguística computacional, particularmente para regras fonológicas e morfológicas da forma $A \to B / L \_ R$. Aqui, cadeias de uma linguagem regular $A$ são substituídas por $B$ dentro do contexto de linguagens regulares $L$ e $R$. Compilar tais regras gerais em FSTs é computacionalmente complexo devido à sobreposição de correspondências (matches), múltiplos contextos e à necessidade de lidar com várias preferências (por exemplo, correspondência à esquerda, mais longa ou mais curta). Métodos de compilação tradicionais, como os de Kaplan e Kay ou Karttunen, dependem de composições intrincadas envolvendo marcadores auxiliares para restringir os locais de reescrita. Essas abordagens frequentemente resultam em fórmulas complexas e não uniformes, difíceis de estender para recursos avançados como reescrita paralela, transduções arbitrárias ou regras ponderadas.

Metodologia
Os autores propõem um esquema de compilação baseado no "truque do pioramento" (worsening trick), uma estratégia aplicada anteriormente a conjuntos e transduções regulares. O método opera em três estágios transparentes para compilar uma regra $A \to B / L \_ R$:

1. Geração de Candidatos ($T_{base}$): O sistema gera todos os possíveis candidatos de reescrita ao pontuar os potenciais locais de transdução. Isso é alcançado construindo um transdutor base que permite que símbolos do alfabeto de entrada $\Sigma$ passem inalterados ou sejam substituídos por cadeias de $B$ dentro de colchetes $< \dots >$ representando a transdução $A:B$. Fronteiras de palavras são explicitamente marcadas com # para tratar contextos de borda de forma uniforme.
2. Restrição de Contexto ($L_{context}$): Candidatos contendo locais de reescrita em contextos ilícitos são filtrados. Em vez de usar fórmulas exponenciais para múltiplos contextos, os autores empregam uma técnica de "posição pontilhada" (Yli-Järä e Koskenniemi). Um símbolo auxiliar · é usado para marcar um único local de reescrita, e uma linguagem $K$ é construída para representar cadeias onde esta posição marcada é cercada por contextos válidos ($L$ e $R$). A interseção dos contextos válidos com o conjunto de candidatos resulta no conjunto de reescritas legais e opcionais.
3. Filtragem de Preferência (Pioramento): Para impor a reescrita obrigatória e preferências específicas (por exemplo, à esquerda, mais longa ou mais curta), o sistema define um transdutor de "pioramento" ($W$). Este transdutor mapeia um candidato "melhor" para um "pior", removendo ou deslocando os colchetes de reescrita (por exemplo, desfazendo uma reescrita ou encurtando um intervalo). O transdutor final é construído filtrando qualquer candidato que possa ser estritamente pior ao aplicar $W$. Matematicamente, para um conjunto de candidatos $C$ e um piorador $W$, o conjunto ótimo é $C \cap \neg \text{range}(C \circ W)$.

Este framework é implementado no PyFoma e suporta:

• Múltiplos Contextos: Tratados via união na linguagem de posição pontilhada.
• Reescrita Direcionada: Preferências como à esquerda, mais longa ou mais curta são codificadas por transdutores de pioramento específicos ($W_{left}$, $W_{long}$, $W_{short}$).
• Transduções Arbitrárias: O $T$ de entrada não precisa ser um simples produto cartesiano; pode ser qualquer FST.
• Reescrita Paralela: Múltiplas regras são tratadas usando colchetes indexados, com restrição de contexto e pioramento aplicados por índice.
• Pesos: A construção funciona dentro do semiring tropical, pois os pioradores filtram os candidatos sem alterar seus pesos atribuídos.
• Tratamento de Épsilon: Um filtro específico evita pares de colchetes vazios consecutivos para restringir inserções de épsilon a locais únicos por fronteira.

Principais Contribuições

• Uniformidade e Compacidade: O artigo apresenta uma formulação onde a lógica de compilação é expressa com fórmulas substancialmente mais curtas e uniformes comparadas às abordagens clássicas pesadas em marcadores ou de múltiplas fitas.
• Extensibilidade: A construção estende-se naturalmente para modalidades complexas (regras paralelas, pesos, marcação, verificação de contexto no lado da saída) sem exigir novos tipos de regras ou maquinaria auxiliar.
• Implementação e Validação: Os autores implementaram o compilador no PyFoma. A validação foi realizada contra o estabelecido compilador foma baseado em C, utilizando uma coleção de 31 gramáticas (427 regras) e um conjunto de regressão automatizado de 2.217 casos.
• Equivalência: Em todos os casos testados onde a semântica coincide, os transdutores resultantes são estruturalmente idênticos aos produzidos pelo foma (diferindo apenas na numeração de estados), confirmando a correção da abordagem baseada em pioramento.

Significância e Alegações
O artigo afirma que o truque do pioramento fornece uma alternativa algébrica robusta para tarefas de seleção procedural em fonologia de estados finitos. Ao gerar um conjunto regular de candidatos e filtrá-los via uma relação de pioramento, ordens de preferência complexas podem ser codificadas declarativamente dentro do cálculo regular. Os autores afirmam que esta abordagem não apenas reproduz a semântica estabelecida dos compiladores clássicos, mas também simplifica a extensão teórica e prática de sistemas de reescrita. A técnica é apresentada não meramente como uma ferramenta de compilação, mas como um padrão de design de estados finitos geral para extrair subconjuntos preferidos de linguagens e relações regulares (por exemplo, representantes mínimos ou máximos). O trabalho reforça a utilidade do truque do pioramento além de suas aplicações anteriores na Teoria da Otimalidade de estados finitos, demonstrando sua eficácia em lidar com todo o espectro das modalidades clássicas de regras de reescrita.