Background
| Timeline | Degree | Affliation |
|---|---|---|
| 2019 - Present | Ph.D |
Indian Institute of Technology Goa |
| 2017 - 2019 | Member of Technical Staff |
Oracle India Pvt Limited, Bangalore |
| 2016 - 2017 | Associate Quality Assurance Engineer |
Oracle India Pvt Limited, Bangalore |
| 2012 - 2016 | B.Tech |
College of Engineering Trivandrum, Kerala |
| 2010 - 2012 | Class 11-12 |
St. Antony's Public School, Kanjirapally |
| 2000 - 2010 | Class 1-10 |
Kendriya Vidyalaya |
Publications
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.
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.
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.
Teaching
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.