Hamming distance between finite transducers

Luc Dartois, Pierre-Cyrille Héam, Ismaël Jecker, Silvio Vescovo · 2026

Read Hamming distance between finite transducers by Luc Dartois, Pierre-Cyrille Héam, Ismaël Jecker, Silvio Vescovo (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-2604-25398.txt.

Introduction

Dartois and three colleagues study bounded deviation of non-deterministic finite transducers under Hamming distance. The bounded comparison task asks whether two transducers yield words within Hamming distance k for every input. It is known decidable in polynomial time for fixed k, and in co-NP otherwise. They show it is NL-complete for fixed k, co-NP-complete for binary k, and DP-complete for exact distance k. They also prove bounded comparison caps max distance at quadratic in the size of both transducers.

Catalog record

CREATORLuc Dartois, Pierre-Cyrille Héam, Ismaël Jecker, Silvio Vescovo
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47992
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.25398

Browse the full library · About the Tower of Babel

Full text

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

Hamming distance between finite transducers Luc Dartois, Pierre-Cyrille Héam, Ismaël Jecker, Silvio Vescovo Abstract We study bounded deviation of non-deterministic finite transducers under the Hamming distance: the bounded comparison problem asks, given two transducers and k ∈ ℕ k\in\mathbb{N} , whether for every input the two transducers produce words at Hamming distance at most k k . This problem is known to be decidable in polynomial time when k k is fixed, and in co-NP otherwise. We show that the problem is NL-complete when k k is fixed, co-NP-complete when k k is given in binary, and it is DP-complete to decide if the distance is exactly k k . We also prove that if the two transducers have bounded comparison, then the maximal distance is at most quadratic in the size of both transducers, and that this bound is asymptotically tight. We prove the results on deviations problem, which asks similar questions on the distance of the pairs of input and output of a single transducer, and show that these two families of problems are logspace many-one equivalent. Université Marie et Louis Pasteur, CNRS, institut FEMTO-ST, F- 25000 Besançon, [email protected] Université Marie et Louis Pasteur, CNRS, institut FEMTO-ST, F- 25000 Besançon, France [email protected] Université Marie et Louis Pasteur, CNRS, institut FEMTO-ST, F- 25000 Besançon, France [email protected] research was partially funded by the Agence Nationale de la Recherche (ANR) grant ANR-25-CE48-2447 FAVOR Université Marie et Louis Pasteur, CNRS, institut FEMTO-ST, F- 25000 Besançon, France [email protected] ccs Theory of computation Transducers keywords Transducers, Hamming distance, NL-completeness, DP-completeness † † runningauthor: L. Dartois, P.-C. Héam, I. Jecker, and S. Vescovo † † copyright: Luc Dartois, Pierre-Cyrille Héam, Ismaël Jecker, Silvio Vescovo † † editors: John Q. Open and Joan R. Access † † event-title: Mathematical Foundations of Computer Science † † event-shorttitle: MFCS † † event-acronym: MFCS † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Finite-state transducers are a fundamental model for describing transformations between words. Studied since the early days of computer science, these machines, initially known as generalised sequential machines [ 17 , 6 ] , are obtained by equipping transitions of finite-state automata with output words. Whereas automata recognise languages , transducers recognise binary relations between input and output words, called rational relations . We refer to [ 14 , 5 ] and the reference therein for a comprehensive overview of this model. As is standard in automata theory, classical decision problems on transducers are inherently Boolean (e.g., equivalence, or determinisability). To move beyond this qualitative setting towards quantitative questions, we need to determine a meaningful notion of distance between transducers . A key requirement is that such a notion should correspond to algorithmically tractable decision problems to support effective analysis. Lifting distances from words to transducers yields a natural candidate satisfying these requirements. A common way of comparing two words u and v is through their edit distance d(u,v) , defined as the minimum number of elementary operations, called edits , required to transform u into v . Allowing different edits induce different distances. The most well-known, called Levenshtein distance [ 12 ] , allows insertions, deletions and substitutions, and numerous variants arise by restricting operations or assigning them weights. In this work, we focus on the Hamming distance [ 7 ] , where the only operation allowed is the substitution of a letter by another. Beyond words, edit distances have been extended to richer structures. The distance between two languages is typically defined as the minimal [ 9 ] or average [ 13 ] distance between pairs of words drawn from each language. More recently, edit distances have been lifted to rational relations [ 1 , 4 ] . In this setting, the perspective shifts: rather than witnessing proximity via the existence of a close pair, uniform closeness is required among all pairs of outputs associated with the same input. Formally, given two relations R_{1} and R_{2} , their distance is defined as \infty if their domains are distinct, and otherwise we let d(R_{1},R_{2})=\sup{}\{d(v_{1},v_{2})\mid(u,v_{1})\in R_{2}\text{ and }(u,v_{2})\in R_{2}\text{ for some }u\in\Sigma^{*}\}\in\mathbb{N}\cup\{\infty\}. This worst-case viewpoint is well-suited to quantitative verification, as it can capture guarantees on the deviation from an ideal behavior. This distance between relations leads naturally to three fundamental decision problems: determining whether the distance is finite, whether it is bounded by a given threshold, and whether it is exactly equal to a given value. Bounded Comparison Problem Input: Two NFTs \mathcal{T}_{1},\mathcal{T}_{2} with \dom(R_{\mathcal{T}_{1}})=\dom(R_{\mathcal{T}_{2}}) . Output: True if d(R_{\mathcal{T}_{1}},R_{\mathcal{T}_{2}})<\infty , False otherwise. Threshold-bounded Comparison Problem Input: Two NFTs \mathcal{T}_{1},\mathcal{T}_{2} with \dom(R_{\mathcal{T}_{1}})=\dom(R_{\mathcal{T}_{2}}) , and k\in\mathbb{N} encoded in binary. Output: True if d(R_{\mathcal{T}_{1}},R_{\mathcal{T}_{2}})\leqslant k , False otherwise. Exact Comparison Problem Input: Two NFTs \mathcal{T}_{1},\mathcal{T}_{2} with \dom(R_{\mathcal{T}_{1}})=\dom(R_{\mathcal{T}_{2}}) , and k\in\mathbb{N} encoded in binary. Output: True if d(R_{\mathcal{T}_{1}},R_{\mathcal{T}_{2}})=k , False otherwise. Restricting the inputs to transducers with identical domains is natural in this setting. Indeed, if \dom(R_{\mathcal{T}_{1}})\neq\dom(R_{\mathcal{T}_{2}}) , then the distance d(R_{\mathcal{T}_{1}},R_{\mathcal{T}_{2}}) is infinite by definition, making the comparison trivial. Moreover, this restriction allows us to isolate the intrinsic complexity of the comparison problems. Without it, one would first need to check whether the domains coincide, which is PSpace -complete and would therefore dominate the overall complexity. Contributions and organisation of the paper. In this paper we approach these problems from a different perspective: instead of comparing the outputs of two relations we compare the input and output of a single relation. Formally, given a binary relation R , the deviation of R is the maximal Hamming distance between input and output over all pairs in R : \textsf{dev}(R)=\sup{}\{d(u,v)|(u,v)\in R\}\in\mathbb{N}\cup\{\infty\}. This notion naturally gives rise the the following decision problems. Bounded Deviation Problem Input: An NFT \mathcal{T} . Output: True if \textsf{dev}(R_{\mathcal{T}})<\infty , False otherwise. Threshold-bounded Deviation Problem Input: An NFT \mathcal{T} and k\in\mathbb{N} encoded in binary. Output: True if \textsf{dev}(R_{\mathcal{T}})\leqslant k , False otherwise. Exact Deviation Problem Input: An NFT \mathcal{T} and k\in\mathbb{N} encoded in binary. Output: True if \textsf{dev}(R_{\mathcal{T}})=k , False otherwise. We first show in that these problems are equivalent to their comparison counterparts. Theorem 1 . The Bounded, Threshold-bounded and Exact Deviation Problems are logspace many-one equivalent to the corresponding Comparison Problems. Theorem 1 is proved in Section 3 , where we show how to construct, from two transducers \mathcal{T}_{1},\mathcal{T}_{2} , a single transducer \mathcal{T} such that \textsf{dev}(\mathcal{T})=d(\mathcal{T}_{1},\mathcal{T}_{2}) (Proposition 3 ), and conversely how to construct, from a transducer \mathcal{T} , a pair of transducers \mathcal{T}_{1},\mathcal{T}_{2} such that \textsf{dev}(\mathcal{T})=d(\mathcal{T}_{1},\mathcal{T}_{2}) (Proposition 3 ). We then establish tight complexity bounds for all problems. Theorem 2 . The Bounded Deviation Problem for the Hamming distance is NL-complete. Theorem 3 . The Threshold-bounded Deviation Problem for the Hamming distance is: • co-NP-complete when k is part of the input; • NL-complete for every fixed k\geqslant 1 . The DP complexity class, for difference polynomial time is first defined in [ 15 , S. 2] as the class of the problems that are expressed as the difference between two NP problems. Alternatively, it consists of problems that can be defined as the intersection of an NP problem and a co-NP problem. Note that DP contains both NP and co-NP. Theorem 4 .

Read the complete text