Tata Institute of Fundamental Research

Approximate Problems for Finite Transducers

STCS Student Seminar
Speaker: Saina Sunny (IIT Goa)
Organiser: Pranshu Gaba
Date: Friday, 18 Jul 2025, 16:00 to 17:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract: 

Finite (word) state transducers extend finite state automata by defining a binary relation over finite words, called rational relation. If the rational relation is the graph of a function, this function is said to be rational. The class of sequential functions is a strict subclass of rational functions, defined as the functions recognised by input-deterministic finite state transducers. The class membership problems between those classes are known to be decidable. In this talk, I present approximate versions of these problems and show they are decidable as well. This includes the approximate functionality problem, which asks whether given a rational relation (by a transducer), is it close to a rational function, and the approximate determinisation problem, which asks whether a given rational function is close to a sequential function. Closeness is measured using a notion of distance between functions or relations.