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

Resumen Técnico: Compilación de Reglas de Reescritura a Transductores de Estados Finitos con el Truco del Empeoramiento

Planteamiento del Problema
Los transductores de estados finitos (FST) son fundamentales para modelar la reescritura de cadenas en la lingüística computacional, particularmente para las reglas fonológicas y morfológicas de la forma $A \to B / L \_ R$. Aquí, las cadenas de un lenguaje regular $A$ son reemplazadas por $B$ dentro del contexto de los lenguajes regulares $L$ y $R$. Compilar tales reglas generales en FSTs es computacionalmente complejo debido a la superposición de coincidencias, múltiples contextos y la necesidad de manejar diversas preferencias (por ejemplo, coincidencias de la izquierda, de la más larga o de la más corta). Los métodos de compilación tradicionales, como los de Kaplan y Kay o Karttunen, dependen de composiciones intrincadas que involucran marcadores auxiliares para restringir los sitios de reescritura. Estos enfoques suelen resultar en fórmulas complejas y no uniformes que son difíciles de extender a características avanzadas como la reescritura paralela, las transducciones arbitrarias o las reglas ponderadas.

Metodología
Los autores proponen un esquema de compilación basado en el "truco del empeoramiento" (worsening trick), una estrategia aplicada previamente a conjuntos y transducciones regulares. El método opera en tres etapas transparentes para compilar una regla $A \to B / L \_ R$:

1. Generación de Candidatos ($T_{base}$): El sistema genera todos los posibles candidatos de reescritura mediante el delimitado de los sitios potenciales de transducción. Esto se logra construyendo un transductor base que permite que los símbolos del alfabeto de entrada $\Sigma$ pasen sin cambios o sean reemplazados por cadenas de $B$ dentro de corchetes $< \dots >$ que representan la transducción $A:B$. Los límites de palabra se marcan explícitamente con # para tratar los contextos de borde de manera uniforme.
2. Restricción de Contexto ($L_{context}$): Se filtran los candidatos que contienen sitios de reescritura en contextos ilícitos. En lugar de utilizar fórmulas exponenciales para múltiples contextos, los autores emplean una técnica de "posición punteada" (Yli-Jyrä y Koskenniemi). Se utiliza un símbolo auxiliar · para marcar un único sitio de reescritura, y se construye un lenguaje $K$ que representa cadenas donde esta posición marcada está rodeada por contextos válidos ($L$ y $R$). La intersección de los contextos válidos con el conjunto de candidatos produce el conjunto de reescrituras legales y opcionales.
3. Filtrado de Preferencias (Empeoramiento): Para imponer la reescritura obligatoria y preferencias específicas (por ejemplo, la de la izquierda, la más larga o la más corta), el sistema define un transductor de "empeoramiento" ($W$). Este transductor mapea un candidato "mejor" a uno "peor" mediante la eliminación o el desplazamiento de los corchetes de reescritura (por ejemplo, deshaciendo una reescritura o acortando un intervalo). El transductor final se construye filtrando cualquier candidato que pueda ser estrictamente peor al aplicar $W$. Matemáticamente, para un conjunto de candidatos $C$ y un empeorador $W$, el conjunto óptimo es $C \cap \neg \text{range}(C \circ W)$.

Este marco de trabajo está implementado en PyFoma y soporta:

• Múltiples Contextos: Manejados mediante la unión en el lenguaje de posición punteada.
• Reescritura Dirigida: Las preferencias como la de la izquierda, la más larga o la más corta se codifican mediante transductores de empeoramiento específicos ($W_{left}$, $W_{long}$, $W_{short}$).
• Transducciones Arbitrarias: El elemento de entrada $T$ no necesita ser un simple producto cartesiano; puede ser cualquier FST.
• Reescritura Paralela: Múltiples reglas se manejan utilizando corchetes indexados, aplicando la restricción de contexto y el empeoramiento por cada índice.
• Pesos: La construcción funciona dentro del semiring tropical, ya que los empeoradores filtran los candidatos sin alterar sus pesos asignados.
• Manejo de Épsilon: Un filtro específico evita pares de corchetes vacíos consecutivos para restringir las inserciones de épsilon a sitios únicos por frontera.

Contribuciones Clave

• Uniformidad y Compacidad: El artículo presenta una formulación donde la lógica de compilación se expresa con fórmulas sustancialmente más cortas y uniformes en comparación con los enfoques clásicos cargados de marcadores o de múltiples cintas.
• Extensibilidad: La construcción se extiende naturalmente a modalidades complejas (reglas paralelas, pesos, marcado, verificación de contexto en el lado de salida) sin requerir nuevos tipos de reglas o maquinaria auxiliar.
• Implementación y Validación: Los autores implementaron el compilador en PyFoma. La validación se realizó contra el compilador establecido en C llamado foma utilizando una colección de 31 gramáticas (427 reglas) y un conjunto de pruebas de regresión automatizado de 2,217 casos.
• Equivalencia: En todos los casos donde la semántica coincide, los transductores resultantes son estructuralmente idénticos a los producidos por foma (diferenciándose solo en la numeración de estados), confirmando la corrección del enfoque basado en el empeoramiento.

Significado y Reivindicaciones
El artículo sostiene que el truco del empeoramiento proporciona una alternativa algebraica robusta a las tareas de selección procedimental en la fonología de estados finitos. Al generar un conjunto regular de candidatos y filtrarlos mediante una relación de empeoramiento, se pueden codificar órdenes de preferencia complejos de manera declarativa dentro del cálculo regular. Los autores afirman que este enfoque no solo reproduce la semántica establecida de los compiladores clásicos, sino que también simplifica la extensión teórica y práctica de los sistemas de reescritura. La técnica se presenta no meramente como una herramienta de compilación, sino como un patrón de diseño general de estados finitos para extraer subconjuntos preferidos de lenguajes y relaciones regulares (por ejemplo, representantes mínimos o máximos). El trabajo refuerza la utilidad del truco del empeoramiento más allá de sus aplicaciones previas en la Teoría de la Optimalidad de estados finitos, demostrando su eficacia para manejar todo el especto de las modalidades de reglas de reescritura clásicas.