On the edit distance between transducers

Apr 19 16:00 ₂₀₂₃

Abstract: 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 Amaldev Manuel and Saina Sunny.

Aiswarya will be at LMF from 2 April to 2 June 2023 as a Visiting Professor of ENS Paris-Saclay.