Awarded FRS-FNRS Mobility and Congress funding for participating in Autobóz 2026
Postdoctoral Researcher
Saina Sunny
Theoretical computer science researcher working across formal methods, automata theory, transducers, and formal languages.
- saina.sunny [at] ulb [dot] be
- Current Role
- Postdoctoral Researcher
- Affiliation
- Université libre de Bruxelles
- Research Group
- Formal Methods and Verification
About Me
Researcher in formal methods and theoretical computer science.
I am a post-doctoral researcher in the Formal Methods and Verification research group at Université libre de Bruxelles, working with Prof. Emmanuel Filiot and Prof. Guillermo A. Pérez on a research project funded by FWO and FNRS.
I did my Ph.D. in Theoretical Computer Science in the School of Mathematics and Computer Science at Indian Institute of Technology Goa, supervised by Dr. Amaldev Manuel.
Before my Ph.D., I did my B.Tech in Computer Science and Engineering from the College of Engineering Trivandrum, Kerala and worked for 3 years at Oracle India Pvt. Ltd..
My research interests spans the theoretical foundations of computer science, particularly automata theory and formal languages. Outside research, I enjoy teaching, badminton, swimming, and exploring new places.
Research Output
Publications
2026 Edit Distance of Fnite-Valued Transducers 52nd EATCS International Colloquium on Automata, Languages and Programming (ICALP 2026)
Abstract
Transducers generalise automata by producing output word(s) for each input word, thereby defining a relation over words. A transducer is said to be finite-valued if, for every input word, it produces at most k output words, for some constant k. If k=1, then the transducer is said to be functional. The edit distance between two transducers is the minimal number of edits required to transform every output of one transducer into some output of the other, for each input word. This notion has been studied for functional transducers, where it is shown to be computable. However, it is uncomputable for transducers in general. In this work, we show the computability of the edit distance of finite-valued transducers, a class that is strictly more expressive than functional transducers.
Download2025 Approximate Problems for Finite Transducers 52nd EATCS International Colloquium on Automata, Languages and Programming (ICALP 2025)
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. We consider 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. We prove decidability results for several classical distances, including Hamming and Levenshtein edit distance. Finally, we investigate the approximate uniformisation problem, which asks, given a rational relation R, whether there exists a sequential function that is close to some function uniformising R. As its exact version, we prove that this problem is undecidable.
Download2024 Deciding Conjugacy of a Rational Relation (Extended Abstract) 28th International Conference on Developments in Language Theory (DLT 2024)
Abstract
A relation on the free monoid is conjugate if each pair of words in the relation is conjugate, i.e., cyclic shifts of each other. We show that checking whether a rational relation is conjugate is decidable. This extended abstract outlines the proof of this fact. A result of independent interest is a generalisation of the classical Lyndon-Schützenberger theorem from word combinatorics that equates conjugacy of a pair of words (u, v) and the existence of a word z (called a witness) such that uz=zv.
Download2024 Edit Distance of Finite State Transducers 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024)
Abstract
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.
DownloadBackground
Career Timeline
-
Postdoctoral Researcher
Université Libre de Bruxelles
-
Ph.D
Indian Institute of Technology Goa
-
Member of Technical Staff
Oracle India Pvt Limited, Bangalore
-
Associate Quality Assurance Engineer
Oracle India Pvt Limited, Bangalore
-
B.Tech
College of Engineering Trivandrum, Kerala
-
Class 11-12
St. Antony's Public School, Kanjirapally
-
Class 1-10
Kendriya Vidyalaya
Teaching
Teaching Assistant Experience
I served as a Teaching Assistant at IIT Goa from 2020 to 2024 as part of my PhD institute fellowship. During this period, I primarily assisted with the Theory of Computation and Programming Language Paradigms courses, which were offered to third-year B.Tech students at IIT Goa.
News
Recent Updates
Presented our work on "Theory of Hanoi omega-automata and games" in the CFV Seminar at ULB, Belgium.
Our paper titled "Edit distance of finite-valued transducers" got accepted for publication at ICALP 2026.
Gave a talk on "Approximate problems for finite transducers" in the Automata Seminar at IRIF, Paris.
Joined Université libre de Bruxelles (ULB) as a Postdoctoral Researcher.
Presented "Approximate problems for finite transducers" at Highlights of Logic, Games and Automata (Highlights 2025), delivered online".
Successfully defended my Ph.D. :-).
Visited TIFR from 16-22 July and presented the work on "Approximate problems for finite transducers".
Presented paper "Approximate problems for finite transducers" at ICALP 2025 in Aarhus University, Denmark".
Was part of the STCS Vigyan Vidushi 2025 mentoring session as an invited mentor.
ACM/IARCS travel grant approved for ICALP 2025.
Received ACM-W scholarship to attend ICALP 2025.
Paper "Approximate Problems for Finite Transducers" accepted at ICALP 2025, Aarhus, Denmark (July 8-11).
Presented poster at Goa Research Scholar Meet 2025, Panjim, organized by Vidnyan Dhara.
Gave a lightning talk and presented a poster at ACM India ARCS 2025, PSG Tech, Coimbatore.
Invited to present poster on "Edit Distance of Finite-State Transducers" at ACM India ARCS 2025.
Invited to submit full version of "Deciding Conjugacy of a Rational Relation" to Information and Computation special issue for DLT.
Gave a talk at Highlights of Logic, Games and Automata 2024, LaBRI, University of Bordeaux, France.
Gave a talk at Université libre de Bruxelles, Belgium.
Gave talks at both Women in Logic Workshop and ICALP in Tallinn, Estonia.
Submission to Highlights 2024 accepted for presentation.
Attended 10th Indian School of Logic and its Application at IIT Goa.
Received ACM/IARCS travel grant for ICALP 2024 attendance.
Received WiL funding to attend Women in Logic 2024 workshop.
Our paper "Deciding Conjugacy of a Rational Relation" accepted for presentation at Women in Logic 2024.
Invited to present "Edit Distance of Finite State Transducers" at Highlights of Language Theory, DLT 2024.
Our paper "Deciding Conjugacy of a Rational Relation" accepted for presentation and proceedings at DLT 2024.
Our paper "Edit Distance of Finite State Transducers" accepted for publication at ICALP 2024, Tallinn, Estonia (July 8-12).
Posters and Slides