Saina Sunny

Given a metric over words, define the distance between two transducers with identical domain as the supremum of the distances of their respective outputs over all inputs. This is a useful generalisation for comparing transducers that goes beyond the equivalence problem. Two transducers are said to be close (resp. k-close) if their distance is bounded (resp. at most k). We will discuss the decidability of the problem that asks whether two given transducers are close (resp. k-close), for common edit distances. This is a joint work with C.Aiswarya (CMI) and Amaldev Manuel (IIT Goa).

For a metric over words, we define the distance between two transducers with identical domain as the supremum of the distances of their respective outputs over all inputs. We argue that this is a useful generalisation for comparing transducers that goes beyond the equivalence problem. Two transducers are said to be \emph{close} (\textit{resp.} $k$-close) with respect to a metric if their distance is bounded (\textit{resp.} at most $k$). Computing distance between transducers is equivalent to deciding closeness and $k$-closeness, over integer-valued metrics. We show that closeness and $k$-closeness are decidable for rational transducers w.r.t.~common edit distances. Hence the distances with respect to them are also computable. The proof relies on a generalisation of theorems of Lyndon-Sch\"utzenberger from combinatorics of words. Stated concisely, the theorem reads that a sumfree (generated by an regular expression free of unions) set of pairs is conjugate if and only if there is a word witnessing the conjugacy of all the pairs.An interesting corollary of our results is that it can decided if the outputs of two sequential or rational transducers are conjugates for all inputs.