CS Faculty Talks Date: Tuesday, 8 October 2024 Time: 12:00  12:50 PM Venue: Seminar Hall Edit Distance of Finite State Transducers C. Aiswarya Chennai Mathematical Institute. 08102024 Abstract We lift metrics over words to metrics over wordtoword transductions, by defining the distance between two transductions as the supremum of the distances of their respective outputs over all inputs. This allows to compare transducers beyond equivalence. Two transducers are close (resp. kclose) with respect to a metric if their distance is finite (resp. at most k). Over integervalued metrics computing the distance between transducers is equivalent to deciding the closeness and kcloseness problems. For common integervalued edit distances such as, Hamming, transposition, conjugacy and Levenshtein family of distances, we show that the closeness and the kcloseness problems are decidable for functional transducers. Hence, the distance with respect to these metrics is also computable. Finally, we relate the notion of distance between functions to the no tions of diameter of a relation and index of a relation in another. We show that computing edit distance between functional transducers is equivalent to computing diameter of a rational relation and both are a specific instance of the index problem of rational relations. This is a joint work with Amaldev Manuel and Saina Sunny (ICALPâ€™24).
