2026-07-31T01:15:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20268 2024-07-02T07:52:55Z ddc:004 open_access

Edit Distance of Finite State Transducers Aiswarya, C. Manuel, Amaldev Sunny, Saina transducers edit distance conjugacy We lift metrics over words to metrics over word-to-word 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. k-close) with respect to a metric if their distance is finite (resp. at most k). Over integer-valued metrics computing the distance between transducers is equivalent to deciding the closeness and k-closeness problems. For common integer-valued edit distances such as, Hamming, transposition, conjugacy and Levenshtein family of distances, we show that the closeness and the k-closeness 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 notions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik C. Aiswarya and Amaldev Manuel and Saina Sunny 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.125 urn:nbn:de:0030-drops-202682 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.125 eng https://creativecommons.org/licenses/by/4.0/legalcode