Edit Distance of Finite-Valued Transducers
Prince Mathew, Saina Sunny · 2026
Read Edit Distance of Finite-Valued Transducers by Prince Mathew, Saina Sunny (2026) 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-2605-06269.txt.
Introduction
Prince Mathew and Saina Sunny prove that the edit distance between finite-valued transducers is computable. Transducers generalize automata by producing output words for each input word, defining a relation between strings. A transducer is finite valued when every input yields at most a fixed number of outputs. It is functional when that number is one, the special case where edit distance was already known to be computable.
For transducers in general, the same question is uncomputable, so the boundary of what can be decided matters for formal language theory. Finite valued transducers are strictly more expressive than functional ones, which makes the extension substantive rather than cosmetic. The authors show the minimal number of edits needed to turn every output of one such transducer into an output of the other can always be computed.
Catalog record
| CREATOR | Prince Mathew, Saina Sunny |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.06269
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Edit Distance of Finite-Valued Transducers Prince Mathew, Saina Sunny 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 k output words, for some constant k k . If k = 1 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. Université libre de Bruxelles, [email protected] Université libre de Bruxelles, [email protected] We would like to thank all the anonymous reviewers for their in-depth feedback which contributed to improving this paper. ccs Theory of computation Transducers ccs Theory of computation Quantitative automata keywords Edit distance, Finite state transducers, Rational relations, Finite-valued, Multi-sequential † † runningauthor: P. Mathew, and S. Sunny † † copyright: Prince Mathew and Saina Sunny † † editors: Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis † † event-title: 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) † † event-shorttitle: ICALP 2026 † † event-acronym: ICALP † † year: 2026 † † event-date: July 7–10, 2026 † † event-location: Royal Holloway, University of London, Egham, United Kingdom † † series-volume: 374 † † articleno: 189 1 Introduction The theory of automata and transducers provides a rich foundation for modelling and reasoning about languages and relations and has numerous applications, particularly in program synthesis and the formal verification of hardware and software systems. While automata map words to Boolean values, word transducers extend this framework by modelling transformations: they read input words and produce output words using finite memory, thereby defining relations between words, known as rational relations. Their study dates back to the early days of computer science, where they were referred to as generalised sequential machines [ 14 , 9 , 13 , 7 ] and the references therein. Their ability to capture input–output behaviour makes them a natural tool in diverse applications such as natural language processing, formal verification, and program analysis. A notable subclass of transducers is that of finite-valued transducers. They compute rational relations where each input word is mapped to at most k output words, for a fixed k\in\mathbb{N} . Such relations are called k -valued (or finite-valued ) rational relations. When k=1 , the rational relation is called a rational function . Many problems that are undecidable in general for transducers become decidable under finite-valuedness. For instance, inclusion and equivalence are undecidable in general [ 8 ] , but become decidable under the finite-valued restriction [ 3 , 21 , 4 ] . The subclass of finite-valued relations is decidable within the class of rational relations, i.e., given a finite state transducer \mathcal{T} , it is decidable in polynomial time whether \mathcal{T} is a finite-valued transducer [ 20 , 15 ] . In fact, it is also decidable in polynomial time to check if \mathcal{T} recognises a k -valued rational relation for a given k\in\mathbb{N} [ 10 , 15 ] . Thus, finite-valued transducers strike a balance between expressive power and algorithmic tractability. Recently, a quantitative notion of distance between transducers was introduced in [ 2 ] by lifting standard word metrics, most notably the edit distance, from words to word-to-word transformations. The edit distance measures the minimum number of edits (such as inserting or deleting a letter, or substituting a letter with another) required to transform one word into another. The edit distance between transducers provides such a quantitative measure: for every input word, it asks how many edits are required to transform every output of one transducer into some output of the other. This notion generalises the classical Boolean equivalence problem of two transducers to a numerical setting, where two transducers are assigned a distance, and are considered close if their distance is finite (reducing to standard equivalence when the distance is zero). This arises naturally in applications such as comparing text-based tools, such as spell checkers or grammatical correction tools. This distance between transducers was used in the study of approximate counterparts of fundamental decision problems for rational relations—such as functionality, determinisability, and uniformisation [ 6 ] . It is shown in [ 2 ] that the edit distance of functional transducers is computable; however, the problem is uncomputable for transducers in general [ 19 ] . This naturally raises the question: Is there an expressive yet well-behaved class of transducers, beyond the functional case, where edit distance remains computable? In this work, we answer this question affirmatively for finite-valued transducers, showing that their edit distance is computable. This result extends the computability of edit distance beyond functional transducers and provides a foundation for approximate reasoning within a class of transducers that is both expressive and practically motivated. The procedure for computing the edit distance between finite-valued transducers exploits the fact that every finite-valued transducer can be decomposed into a finite union of functional transducers [ 21 , 16 ] . We reduce the problem of computing the distance between finite-valued transducers to that of computing the distance between multi-sequential transducers (equivalent to a finite union of sequential transducers — those that are deterministic in the input). This further reduces to a new notion we introduce in this work, called the relative distance between a function and a relation. The relative distance between a function f and a relation R is defined as the least upper bound, over all inputs, of the minimal edit distance between the output of f and some output of R on the same input. Intuitively, this captures how far, in the worst case, the behaviour of f deviates from that of R . Beyond its technical role in our reductions, relative distance also provides a natural framework for approximate verification . In classical (exact) verification of reactive systems (systems that continuously interact with an environment by consuming inputs and producing outputs), it is checked whether the given reactive system (modelled by f ) exactly satisfies a user-defined specification (modelled by R ). The notion of relative distance makes it possible to reason about reactive systems that are “close” to a given specification, which is crucial when exact conformance fails, and minor deviations to the specification are acceptable. In summary, we extend the known results on functional transducers to finite-valued transducers, showing that their edit distance is computable. The techniques we develop not only advance the theory of transducer comparison but also provide tools for approximate reasoning and verification of transducer-defined relations. 2 Preliminaries We now recall the basic notions and notations that will be used throughout the paper. Let \mathbb{N} denote the set of natural numbers. For every k\in\mathbb{N} , we use [k] to denote the set \{1,2,\ldots,k\} . Words and relations. Let A and B denote finite alphabets of letters. A word is a sequence of