Edit Distance of Finite-Valued Transducers

Resumen Técnico: Distancia de Edición de Transductores de Valor Finito

Enunciado del Problema
El artículo aborda la computabilidad de la distancia de edición entre dos transductores de estado finito. Si bien se sabe que la distancia de edición entre transductores funcionales (donde cada entrada se mapea a como máximo una salida) es computable, el problema es generalmente incalculable para transductores arbitrarios. Los autores investigan si esta computabilidad se extiende a la clase de transductores de valor finito, donde cada palabra de entrada se mapea a como máximo $k$ palabras de salida para una constante fija $k$. Esta clase es estrictamente más expresiva que los transductores funcionales, pero conserva la decidibilidad para muchos problemas fundamentales (por ejemplo, inclusión y equivalencia) que son indecidibles en el caso general.

Metodología
La solución propuesta procede mediante una estrategia de reducción que transforma el problema de calcular la distancia entre transductores de valor finito en una serie de subproblemas computables que involucran transductores secuenciales y un concepto métrico recién introducido.

1. Reducción a Transductores Multi-secuenciales:
   Los autores aprovechan el resultado conocido de que cualquier transductor de valor finito puede descomponerse efectivamente en una unión finita de transductores no ambiguos (y por tanto funcionales). Construyen un autómata producto que sincroniza las ejecuciones de todos los transductores componentes de dos transductores de valor finito dados, $T$ y $S$. Esta construcción produce dos transductores multi-secuenciales, $T'$ y $S'$ (uniones finitas de transductores secuenciales/deterministas), tales que la distancia de edición $d(T, S)$ se preserva y es igual a $d(T', S')$.

2. Introducción de la Distancia Relativa:
   Para calcular la distancia entre relaciones multi-secuenciales (que son uniones de funciones secuenciales), los autores introducen el concepto de distancia relativa. La distancia relativa de una función $f$ a una relación $R$, denotada $\vec{d}(f, R)$, se define como el supremo sobre todas las entradas $u$ de la distancia de edición mínima entre $f(u)$ y algún $v \in R(u)$.
   Se demuestra que la distancia entre dos relaciones multi-secuenciales $R = \bigcup f_i$ y $S = \bigcup g_j$ es el máximo de las distancias relativas entre cada función componente y la relación opuesta:
   $$d(R, S) = \max \left( \max_i \vec{d}(f_i, S), \max_j \vec{d}(g_j, R) \right)$$

3. Decidibilidad de la Distancia Relativa:
   La computabilidad de la distancia relativa $\vec{d}(f, R)$ se establece reduciéndola a dos problemas de acotación:

   • Finitud: Decidir si $\vec{d}(f, R) < \infty$.

   • $k$-Finitud: Decidir si $\vec{d}(f, R) \leq k$ para un entero dado $k$.

   • Verificación de Finitud: Los autores construyen un transductor producto $T$ que representa las ejecuciones síncronas de $f$ y los componentes de $R$. Particionan el dominio de $f$ en función de qué componentes de $R$ aceptan la entrada. Para cada partición, analizan los componentes fuertemente conexos (CFC) del transductor producto. Utilizando propiedades de la conjugación de palabras (específicamente, que una distancia de edición infinita acotada implica la conjugación de las salidas de los bucles), demuestran que la distancia relativa es finita si y solo si, para cada camino de CFC en el producto, existe al menos una relación componente cuya salida de bucle es conjugada a la salida de bucle de la función. Esto reduce el problema a verificar la finitud de la distancia entre transductores secuenciales, lo cual es decidible.

   • Verificación de $k$-Finitud: Para decidir si la distancia está acotada por $k$, los autores construyen un autómata finito no determinista (AFN), $A_{C,k}$, que rastrea el presupuesto de edición y los sufijos "sobrantes" no emparejados entre la salida de la función y las salidas de la relación. La distancia relativa es $\leq k$ si y solo si el lenguaje aceptado por $A_{C,k}$ es idéntico al dominio del transductor producto.

Contribuciones y Resultados Clave

• Teorema Principal: La distancia de edición entre dos relaciones racionales de valor finito es computable para métricas de la familia de Levenshtein (Levenshtein, Subsecuencia Común Más Larga y Damerau-Levenshtein).
• Marco Algorítmico: El artículo proporciona un procedimiento constructivo para calcular esta distancia reduciendo el caso de valor finito al caso multi-secuencial, y posteriormente a la distancia relativa entre una función secuencial y una relación multi-secuencial.
• Análisis de Complejidad: Los autores señalan que su procedimiento resulta en una cota superior de 3-EXPSPACE. Esto surge del espacio exponencial requerido para convertir transductores de valor finito en multi-secuenciales, seguido de requisitos de espacio exponencial y doblemente exponencial para los cálculos subsiguientes de distancia relativa. La cota inferior es al menos PSPACE-dura, ya que subsume el problema de equivalencia para autómatas no deterministas.

Significado y Afirmaciones
El artículo afirma extender la decidibilidad conocida de la distancia de edición más allá de los transductores funcionales hacia la clase más amplia de transductores de valor finito. Esto es significativo porque los transductores de valor finito logran un equilibrio entre poder expresivo y tratabilidad algorítmica, capturando muchos escenarios prácticos donde una sola entrada puede producir un conjunto pequeño y acotado de salidas válidas (por ejemplo, en procesamiento del lenguaje natural o síntesis de programas).

Los autores enfatizan que su trabajo proporciona una base para el razonamiento aproximado en sistemas reactivos. En la verificación clásica, un sistema se verifica para una conformidad exacta con una especificación. El concepto de distancia relativa permite razonar sobre sistemas que están "cerca" de una especificación, acomodando desviaciones menores. El artículo no afirma optimizar el algoritmo para la eficiencia, reconociendo la alta complejidad, pero afirma que el resultado establece la posibilidad teórica de calcular estas distancias en una clase de transductores expresiva y motivada por la práctica. También se señala que las técnicas son adaptables a otras métricas de edición, como la distancia de Hamming, con modificaciones menores.