Approximate Problems for Finite Transducers

Emmanuel Filiot, Ismaël Jecker, Khushraj Madnani, Saina Sunny · 2025

Read Approximate Problems for Finite Transducers by Emmanuel Filiot, Ismaël Jecker, Khushraj Madnani, Saina Sunny (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-17299.txt.

Introduction

Emmanuel Filiot, Ismaël Jecker, Khushraj Madnani, and Saina Sunny study near-miss versions of classic questions about finite transducers. Their 2025 paper concerns machines that transform input words into output words. Exact questions, such as whether a machine's relation is truly a function, are known to be decidable.

The authors ask the approximate versions: is a given relation close to a function, or a function close to one a simpler deterministic machine can compute? Closeness is measured by standard distances between words, such as edit distance. They prove these approximate problems are decidable for several distances. One harder variant, finding a simple function near some selector of a relation, stays undecidable, mirroring its exact counterpart. The results map where approximation keeps problems solvable.

Catalog record

CREATOREmmanuel Filiot, Ismaël Jecker, Khushraj Madnani, Saina Sunny
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE114 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-17299

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Approximate Problems for Finite Transducers Emmanuel Filiot, Ismaël Jecker, Khushraj Madnani, Saina Sunny 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 R , whether there exists a sequential function that is close to some function uniformising R R . As its exact version, we prove that this problem is undecidable. Université libre de [email protected]://orcid.org/0000-0002-2520-5630He is a senior research associate at the National Fund for Scientific Research (F.R.S.-FNRS) in Belgium. His work is supported by the FNRS project T011724F. Université de Franche-Comté[email protected]://orcid.org/0000-0002-6527-4470 Max Planck Institute for Software [email protected]://orcid.org/0000-0003-0629-3847 Indian Institute of Technology [email protected]://orcid.org/0009-0005-1366-0168 ccs Theory of computation Transducers ccs Theory of computation Quantitative automata keywords Finite state transducers, Edit distance, Determinisation, Functionality † † runningauthor: E. Filiot, I. Jecker, K. Madnani and S. Sunny 1 Introduction Finite (state) transducers are a fundamental automata model to compute functions from words to words. The literature on finite state transducers is rich, and dates back to the early days of computer science, where they were called generalised sequential machines [ 29 , 20 ] . See also [ 28 , 19 ] and the references therein. Finite state transducers extend finite automata with outputs on their transitions, allowing them to produce none or several symbols. While finite automata recognise languages of (finite) words, finite transducers recognise binary relations from words to words, called rational relations . When the rational relation is the graph of a function, it is called a rational function . This subclass is decidable within the class of rational relations. In particular, given a finite transducer T , it is decidable in PTime whether T recognises a function [ 21 , 10 ] . In that case, T is said to be functional . Beyond the fact that it is a natural restriction, the class of functional transducers is of high importance, as many problems known to be undecidable for transducers (such as inclusion and equivalence), become decidable under the functional restriction. Determinisation It turns out that non-determinism is needed for finite transducers to capture rational functions. A canonical example is the function f_{\sf last}:\{a,b\}^{*}\rightarrow\{a,b\}^{*} that moves the last symbol upfront. For example, f_{\sf last}(ab\underline{b})=\underline{b}ab and f_{\sf last}(ab\underline{a})=\underline{a}ab . Since the number of symbols that have to be read before reading the last symbol is arbitrarily large, a finite transducer recognising f_{\sf last} needs non-determinism to guess the last symbol, as illustrated by the following transducer: q_{0} q_{1} q_{2} q_{3} q_{4} \begin{array}[]{lll}a\mid aa\\ b\mid ab\end{array} \begin{array}[]{l}a\mid ba\\ b\mid bb\end{array} \begin{array}[]{l}a\mid a\\ b\mid b\end{array} \begin{array}[]{l}a\mid a\\ b\mid b\end{array} b\mid\epsilon a\mid\epsilon So non-determinism, unlike finite automata, brings some extra expressive power when it comes to finite transducers. On the other hand, non-determinism also yields some inefficiency issues when the input is received sequentially as a stream, because the whole input may have to be stored in memory until the first output symbol can be produced. This motivates the class of sequential functions , as the rational functions recognised by input-deterministic finite transducers, and the determinisation problem : given an arbitrary finite transducer, does it recognise a sequential function? In other words, can it be (input-) determinised? This well-studied problem is known to be decidable in PTime [ 10 ] . The determinisation problem is a central problem in automata theory. It has been for instance extensively considered for weighted automata [ 27 ] , and a long-standing open problem is whether this problem is decidable for (\mathbb{N},max,+) -automata [ 25 ] . Approximate determinisation The function f_{\sf last} is not sequential, in other words, the latter transducer is not determinisable. It turns out that f_{\sf last} is almost sequential, in the sense that it is close to some sequential function, for instance the identity function {\sf id} . ”Close to” can be defined in different ways, by lifting standard distances between words to functions and relations. Two classical examples are the Hamming distance and the Levenshtein distance, which respectively measure the minimal number of letter substitutions (respectively letter substitutions, insertion and deletion) to rewrite a word into another. A distance d between words is lifted to functions f_{1},f_{2} with the same input domain, by taking the supremum of d(f_{1}(u),f_{2}(u)) for all words u in their domain. Coming back to our example, f_{\sf last} and {\sf id} are close for the edit distance, in the sense that d(f_{\sf last},{\sf id}) is finite for d the edit distance, but they are not close for the Hamming distance. This raises a natural and fundamental problem, called approximate determinisation problem (for a distance d ): given a finite transducer recognising a function f , does there exists a sequential function s such that d(f,s) is finite? The approximate determinisation problem has been extensively studied for weighted automata [ 4 , 8 , 5 ] and quantitative automata [ 6 , 7 ] , but, to the best of our knowledge, nothing was known for transducers. However, if both f and s are given (by finite transducers), checking whether they are close (for various and classical edit distances) is known to be decidable, even if s is rational but not sequential [ 2 ] . This can be seen as the verification variant of approximate determinisation, while approximate determinisation is rather a synthesis problem, for which only f is given, and which asks to generate s if it exists. Contributions In this paper, our main result is the decidability of approximate determinisation of finite transducers, for a family \mathcal{E} of edit distances, which include Hamming and Levenshtein distances. For exact determinisation, determinisable finite transducers are characterised by the so called twinning property ( TP ) [ 10 , 9 , 13 ] , a pattern that requires that the delay between any two outputs on the same input must not increase when taking synchronised cycles of the transducer. As noticed in [ 2 ] , bounded (Levenshtein) edit distance is closely related to the notion of word conjugacy. In this paper, we consider an approximate version of the twinning property ( ATP ), with no constraints on the delay, but instead requires that the output words produced on the synchronised loops are conjugate. It turns out that ATP is not sufficient to characterise approximately determinisable transducers, and an extra property is needed, the strongly connected twinning property ( STP ), which requires that the TP holds within SCCs

Read the complete text