On the edit distance between transducers

Speaker: C. Aiswarya, CMI

Wednesday, 19 April 2023, 16:00, 1Z56 ENS Nord and Zoom

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.