Edit Distance of Finite State Transducers
C. Aiswarya Amaldev Manuel Saina Sunny

Unbiased Estimating Equation on Inverse Divergence and Its Conditions
    
  Masahiro Kobayashi
  Information and Media Center

                    Toyohashi University of Technology

                    Toyohashi, Aichi, Japan

                    Email: kobayashi@imc.tut.ac.jp
  Kazuho Watanabe
  Department of Computer Science and Engineering
 
                    Toyohashi University of Technology

                    Toyohashi, Aichi, Japan

                    Email: wkazuho@cs.tut.ac.jp

    April 29, 2024
============================================================================================================================================================================================================================================================================================================================================================================================================================================




 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. 




§ INTRODUCTION

For meaningfully comparing two words (or sequences, vectors, functions, etc.), it is often necessary to have a measure that quantifies their (dis)similarity. It usually consists of associating a nonnegative integer to two words that indicates how different they are from each other. This usually defines
a distance between words, the most popular of which are edit distances. It is the minimum number of edit operations required to transform one word into another. These operations typically include inserting or deleting a letter, substituting a letter with another,  swapping adjacent letters (transpositions), and cyclic shifts. 
Edit distances are studied in coding   <cit.>, parsing   <cit.>, speech recognition <cit.>,  molecular biology <cit.> etc. Interesting combinatorial problems on words such as the computation of longest common subsequences can be reduced to computing edit distances <cit.>. 
 For a detailed overview of the history and applications of edit distances,  see  <cit.>.

The notion of distance between two words can be lifted naturally to distance between a word and a set of words, or between two sets of words, and so on. There is a long line of research of  this kind: computing the edit distance between two languages — usually defined as the smallest distance between any two pairs from the respective sets.  
 It could be between a word and a regular language <cit.> <cit.>, two regular languages <cit.>, a regular language and itself <cit.>, or a regular language and a context-free language <cit.>. In all these settings there are efficient algorithms for computing the edit distances. 

In this paper, we study the distance between two word-to-word functions (transductions) given by finite state transducers, i.e., automata with output. 
A transducer is a machine that reads an input word and produces one or more output words. They were one of the earliest machines to be studied in automata theory, and in fact finite state automata were first defined as a special case of finite state transducers <cit.>.
Finite state transducers are used in a variety of software and hardware systems such as encoders, decoders, demuxers, spell checkers, text normalizers, schema translators, template code generators, etc. 
 
 
Our aim is to develop a framework to meaningfully compare two transductions beyond equivalence. 
Consider the functions given by the transducers in <Ref>. The transducers _1 and  _2 output the letters at the odd and even positions respectively, while the transducer _3 erases b's in the input. If we were to find the odd one among these three functions, arguably _3 will be picked, with the length of the respective output on any input deviating significantly from that of the others. Our aim is to define a measure that quantifies such distances. 

If we have a metric to compare the output words, we can extend it to transductions as follows. The distance between two transductions is the least upper bound of the distances between their respective outputs on any input word. We assume that their domains are the same, and we set the distance to infinity if this is not the case.  We say that two transductions are close if their distance is finite, and they are k-close if their distance is at most k. We may simply say that two transducers are close (or k-close) instead, to mean that the transductions defined by these transducers are close (or k-close).

We are interested in the following question: Given two finite state transducers, are the transductions defined by them close (or simply are the transducers close)?
Clearly, deciding closeness is a boundedness problem. We show closeness as well as  k-closeness  are decidable for various edit distance metrics, in particular Hamming (letter-to-letter substitutions), transposition (swapping adjacent letters), conjugacy (only cyclic shifts) and Levenshtein family of distances — Longest common subsequence (insertion and deletion), Levenshtein (insertion, deletion and substitution), and Damerau-Levenshtein (insertion, deletion, substitution and adjacent transposition). It turns out that computing distance between transducers is equivalent to deciding closeness and k-closeness over integer-valued metrics (see <Ref>).  Hence for the edit distances mentioned above, the distance between transducers is computable. 


A related notion is that of diameter of a relation. We define it to be the supremum of the distance of every pair in the relation. We are interested in computing the diameter of rational relations over words, that is those given by (not necessarily functional) finite state transducers. A rational relation is said to have bounded diameter (resp. k-bounded diameter) if the diameter of the relation is finite (resp. at most k). It turns out that for every pair of transductions _1 and _2 there is a rational relation R such that for every metric, the diameter of R is same as the distance between _1 and _2. In fact, the converse is also true by virtue of Nivat's theorem (see <Ref>). 
 

Another related notion is that of the  index of a rational relation in the composition closure of another. Let R,S be a rational relation over words. The index of R in the composition  closure of S is defined to be the smallest integer k such that the relation R is contained in the k-fold composition of S. If such a k exists we say that R has the finite index property in the composition closure of S.  We show that the finite index property is undecidable for arbitrary rational relations. However, if S is a metrizable relation (see <Ref>) w.r.t. the edit distances mentioned above, the index of R in the composition closure of S is computable. 



Our decision procedure for k-closeness involves designing a weighted automaton that counts the number of edit operations for transforming one output to the other. We need to check whether there are input instances for which the weight is more than k. We extract a finite state automaton of size exponential in k that achieves this (see <Ref>). This is a generic approach independent of the particular edit operations. However for Hamming and transposition distances, we have a direct polynomial time procedure for deciding k-closeness (see <Ref>). 


Recall that deciding the closeness of transductions is the same as deciding whether the diameter of a rational relation R is bounded. For the latter, consider a transducer recognising R. It turns out that if there are loops in this transducer that produce nonconjugate words (that are not cyclic shifts of each other) then such loops can be iterated to get unbounded diameter/distance. Thus a crucial ingredient in our decision procedure is checking for conjugacy of loops, which is decidable <cit.>. 
 For boundedness w.r.t. Levenshtein distances, we show that this is also a sufficient condition (see <Ref>). For conjugacy distance, we show that the diameter of a rational relation R is bounded if and only if every pair in R is conjugate (see <Ref>). Notice that this is not the case for arbitrary relations.  In the case of Hamming distance, which only includes substitutions, we show that it is sufficient to check if the pairs of words generated by the loops after some shifted delay are identical (see <Ref>). This also holds true for transposition distance, but additionally, we also need to check if the words are permutations of each other (see <Ref>). 




 §.§ Related Work


The adjacent functions in <cit.> is an analogous definition for closeness between transductions  with respect to prefix distance. Two functions f,g : A^* → B^* are adjacent if sup{  d_p(f(w),g(w)) | w ∈(f) ∩(g)  } < ∞. Here, d_p(u,v) = |u| + |v| - 2max{|z| | u,v ∈ zA^*} denotes the prefix distance between two words u and v. The adjacency of two rational functions is used in deciding the sequentiality of a function. It is decidable to check if two given rational functions are adjacent or not <cit.>(Proposition 1).

Another problem that is similar in spirit is the robustness problem. We say a transducer  is robust w.r.t. a distance d if there is a nontrivial relation R between the distance between two input words (say d(u,v)) and distance between their corresponding outputs on  (say d((u),(v))). For instance, R could be Lipschitz continuity — there is some k>0 such that d((u),(v)) ≤ k · d(u,v), or locally Lipschitz continuity — there exists b,k>0 such that if d(u,v)<b then d((u),(v)) ≤ k · d(u,v), etc. Sometimes, weaker notions of distance are considered (for instance by dropping the triangle inequality), and respective distances are called cost or similarity functions. The work <cit.> solves the locally Lipschitz continuity problem for sequential and unambiguous transducers using reversal bounded counter automata. The problem is shown to be undecidable for Lipschitz continuity even for deterministic transducers and the decidability is shown for the class that has a bound on the delay between input and output words <cit.>.


 Frougny and Sakarovitch studied rational relations with bounded delay <cit.>, which is actually our diameter problem for rational relations when the distance over words is measured by their length difference. A problem related to the diameter of a rational relation is almost reflexivity of rational relations studied in <cit.>. A relation R ⊆ A^* × A^* is k-reflexive, for some integer k ≤∞, if every element u of the domain is at a distance at most k from some element of the range v, with (u,v) ∈ R, and vice versa. The relation R is almost reflexive if k < ∞. It is shown undecidable to check if a deterministic rational relation is almost reflexive, or k-reflexive, for any given integer k, with respect to the following – Hamming,  prefix, suffix, subword and Levenshtein edit distances. It is shown decidable for synchronized rational relation w.r.t. Hamming distance.

In 1966, Brzozowski raised the question of finite power property on regular languages —  it takes a regular language L as input and asks whether there exists some positive integer n such that (L + ϵ)^n = L^*. It was solved in 1979 by Hashiguchi <cit.> and Simon <cit.>, independently. We study the finite index property of a rational relation in the iterative composition of another relation.  Notice that the finite index property is different from the finite power property in two respects. One, it is over relations and not languages, and secondly and more importantly, the iteration is obtained by relation composition and not concatenation.



 §.§ Organisation of the Paper

In Section <ref>, we recall the definitions of finite state transducers, metrics on words and edit distances. In Section <ref>, we define the notion of distance between transducers, the diameter of a rational relation, and the index of a rational relation in another. We also establish the relation between these notions and state our results in this section. In Section <ref>, we give the connections with conjugacy and the proof arguments remaining from Section <ref>. Finally, we conclude in Section <ref> with a short discussion on future directions. 



§ PRELIMINARIES


Let A^* denote the set of all finite words over the alphabet A. We use |w| to denote the length of the word w. 
Let w[i  j] denote the factor of w from index i to j where 1 ≤ i ≤ j ≤ |w|. 
A transduction is a function from words to words. 



 §.§ Finite State Transducers



The simplest form of a transducer is a deterministic finite state machine whose each transition and each final state is labelled by a possibly empty output word. Formally, a sequential transducer = ⟨, λ, ο⟩ with input alphabet A and output alphabet B is a deterministic finite state automaton  with two associated output functions λ: Δ→ B^* and ο:F → B^* where Δ and F are the set of transitions and the set of accepting states of  respectively. 

On an input word that is accepted by the automaton, we concatenate the output words produced by the transitions in the unique run of the machine and finally append the end-of-input word of the final state to obtain the output of the machine.
That is to say, if ρ=δ_1 ⋯δ_n is the successful run of  on a word w ∈ A^*, the output of  on w, denoted by (w), is the word λ(ρ)·ο(q) where λ(ρ)= λ(δ_1)⋯λ(δ_n) and q is accepting state reached by the run. Let L() denote the set of words accepted by , called the language of  or the domain of  (denoted as ()). We can see that  defines a function from () to B^*. Functions defined by sequential transducers are called sequential. In the literature, they are known as subsequential functions, introduced by Schützenberger <cit.>. Transducers given in <Ref> are sequential. 


If we allow the finite state automaton  to be nondeterministic, then  no longer defines a function, but a binary relation on A^*× B^*. Such relations are called rational. If the relation is a function, then the transducer is called functional, and the corresponding functions are called rational functions. 
We can restrict the nondeterminism and still compute all rational functions. A finite state automaton is unambiguous if on each input word the machine has at most one run. It is a well-known fact in the theory of transducers that all rational functions  are computed by finite state transducers whose underlying automata are unambiguous <cit.>. Such transducers are called unambiguous transducers.  Clearly sequential functions are a strict subset of rational functions. 
For instance, the function `output the input word if the last letter of the input is an a, otherwise the empty word' is rational but not sequential.


There exist generalisations of rational functions where the underlying automaton is a two-way finite state automaton or equivalently a finite state automaton with registers (corresponding functions are called regular <cit.>), or two-way finite state automaton with pebbles (polyregular functions <cit.>). An overview of the classical theory of transducers is given in <cit.>. In this paper, we restrict our attention to one-way functional transducers.



 §.§ Metric on Words, Edit Distances

Simply put, a metric on a set is used to measure distance between any two elements of the set.  A metric on words over the alphabet A is a function d: A^* × A^* → [0, ∞ ] such that for any words u,v and w in A^*, d(u,v) = 0  u = v (separation), d(u,v) = d(v,u) (symmetry), and d(u,v) ≤ d(u,w) + d(w,v) (triangle inequality). 


A metric is integer-valued if it has range ∪{∞}.
A trivial metric on words is the discrete metric — distance between words u and v, denoted by d_∞(u,v), is 0 if u = v and ∞ otherwise. Another straightforward distance on words is the absolute difference of their lengths (denoted as ). This is a pseudo-metric since the distance between two distinct words can be zero, i.e., does not satisfy the separation property of a metric.


An important class of metrics in the context of word transducers is edit distances. Loosely speaking, edits are operations that transform words, such as inserting a letter, deleting a letter, substitutions (letter-to-letter), adjacent transpositions (swapping adjacent letters), left and right shifts etc. 
For a fixed set of edit operations C, the edit distance with respect to C between words u and v, is the minimum number of edits in C required to transform u to v if it is possible, and ∞ otherwise.   
The common edit distances and their corresponding operations are recalled in Table <ref>.

 Since many of these operations are obtained by combinations of the others, we can relate these metrics. The notation d_1 ≤ d_2 is an abbreviation for d_1(u,v) ≤ d_2(u,v) for all words u,v.
We can also relate the metrics up to boundedness (See <cit.> for a detailed introduction). Let α:→ be a correction function. Usual examples are increments (e.g. x↦ x+2), scaling (e.g. x ↦ 2· x) etc. We extend α to the domain ∪{∞} by letting α(∞)=∞.  
We write d_1 ≲ d_2 to mean that there is some α such that d_1 ≤α∘ d_2. Clearly, if d_1 ≤ d_2 then d_1 ≲ d_2. If d_1 ≲ d_2 and d_2 ≲ d_1, we write d_1 ≈ d_2 (this is known as the cost equivalence or the boundedness equivalence). If two functions f and g are cost-equivalent then f and g are bounded over precisely the same family of subsets (See Proposition 1 of <cit.>).   


 The metrics defined in Table <ref> are related as follows: 


  *  ≤ d ≤ d_∞, for each edit distance metric d∈{d_l,d_h,d_t,d_c,,}

  * d_l ≈≈

  * d_l≤ d_h ≲ d_t

  * d_l ≲ d_c

  * d_c and d_t as well as d_c and d_h are incomparable, i.e., d_h ≴d_c, d_c ≴d_h and d_t ≴d_c, d_t ≴d_c





  * From definition of the metrics.

  * Clearly d_l ≤. Since one substitution can be achieved by an insertion and deletion, ≤ 2· d_l. Hence d_l ≈. Similarly ≤ d_l and since a transposition is equivalent to two substitutions d_l ≤ 2 ·. Therefore d_l ≈.

  * d_l ≤ d_h is obvious. Since a transposition is equivalent to two substitutions d_h ≤ 2 · d_t.

  * Since a cyclic shift is achieved by an insertion and a deletion, d_l ≤ 2· d_c. 
 
  * For the last statement, consider the family of words {((01)^k,(10)^k) | k ≥ 0 }, d_h,d_t →∞, but d_c is 1. Conversely, for the family of words {(10^k1,010^k-11) | k ≥ 1 }, d_t = 1, d_h=2, but d_c is ∞.





§ DISTANCE BETWEEN TRANSDUCTIONS



In this section, we define the notion of distance between two rational functions, the diameter of a rational relation, and the index of a rational relation in another. We establish the relation between these notions and state our results. 



 §.§ Comparing Transducers


We lift a metric over words to the class of word-to-word functions as follows.



Let d be a metric on words over the alphabet B.  Given two  partial functions ,  : A^∗→ B^∗, we define

    d(,) = sup{   d((w), (w))  |   w ∈() }    if () = ()
    ∞    otherwise




 d is a metric on  transductions.




Clearly, since d is a metric on words, d(,)=0 if and only if  and  are the same transductions, and d(,) = d(, )  for transductions  and . Let ,, be three transductions with the output alphabet B. It remains to show that d(,) ≤ d(,) + d(,).
  
Assume the domains of  and  are different. Then, either () ≠() or () ≠(). In both cases, d(,) and 
d(,) + d(,) are ∞. Therefore, assume that the domains of , and  are the same, call it L. Since for each word w in L, d((w),(w)) ≤ d((w),(w)) + d((w),(w)) by virtue of d being a metric, it follows that 


    d(,)        =sup{ d((w),(w))  |  w ∈ L }
          ≤sup{ d((w),(w)) + d((w),(w))   |  w ∈ L }
          ≤sup{d((w),(w))  |  w ∈ L  } + sup{  d((w),(w))   |  w ∈ L  }
          =  d(,) + d(,) .




We can define a notion of distance between word-to-word relations in the above manner, however this distance will not be a metric. In particular d(R,R) will not be 0 for a relation R that is not a (partial) function.
	


Consider the sequential transducers _1 and _2 in <Ref>.
The transducers _1 and  _2 output the letters at the odd and even positions respectively. For any input word u, ||_1(u)| - |_2(u)|| ≤ 1. Hence (_1,_2)= 1. For input word (ab)^n where n > 1, the outputs produced by _1 and _2 are a^n and b^n respectively. Since n substitutions are required to convert a^n to b^n, d_l(a^n,b^n) = n. Therefore, d_h(_1,_2)=∞ as well as d_l(_1,_2)=∞.

 
 
The sequential transducer _4 in <Ref> replaces each block of 0's by a single 0 and each block of 1's by a single 1. Similarly, _5 substitutes a block of 0's by a single 1 and a block of 1's by a single 0. The output words produced by the transducers on any input word is an alternate sequence of 0's and 1's. If _4 outputs 010, then _5 produces its complement, i.e., 101. The Hamming distance between _4 and _5 is ∞, but the Levenshtein distance is 2.




Let d be a distance on words. The value d(,) is an upper bound on how dissimilar the outputs of transducers  and  can be on any input. It is natural to ask the computational and boundedness problems given in Table <ref>. 


Closeness and k-closeness are respectively a boundedness and an upper bound problem on distance. 

Let d be an integer-valued metric. The distance problem w.r.t. d is computable if and only if k-closeness and closeness problems w.r.t. d are decidable.


Clearly, if we can compute the distance w.r.t. d then we can decide k-closeness as well as closeness. For the other direction, given two transducers, we first check if they are close and if it is we perform an exponential search — check if they are k-close for k=2^0, 2^1, 2^2,… till it fails and subsequently perform a binary search on the interval [2^n, 2^n+1], n∈ that contains the distance. 

We say two transducers  and  are close (resp. k-close, for k ≥ 0) w.r.t. d if d(,) < ∞ (resp. d(,) ≤ k).
Closeness with respect to the discrete metric d_∞ is precisely the equivalence problem. 
In the case of edit distances, closeness means that the output of _1 can be converted to the output of _2 by doing a bounded number of edits.

From <Ref>, it is easy to verify that <Ref> holds for transducers as well. If d_1 ≲ d_2, then it is easy to see that if transducers _1 and _2 are not close w.r.t. d_1, then they are not close w.r.t. d_2 either.

The problems in Table <ref> for unambiguous transducers with identical domains can be reduced to that for sequential transducers by considering the cartesian product of the unambiguous transducers.  Given two unambiguous transducers _1 and _2, we obtain the sequential transducers '_1 and '_2 as follows. The  input automata for '_1 and '_2 are the same, call it , which is the cartesian product of the input automata of _1 and _2. 
By treating the transitions of the cartesian product as the input alphabet, we get input determinism. The output functions of '_1 and '_2 are lifted from T_1 and T_2 respectively.


Let d be a distance on words. For each pair of unambiguous transducers _1 and _2 with identical domain, there exist a DFA  and output functions λ_1',ο_1' and λ_2',ο_2' such that  d(_1,_2) = d(_1',_2') where the sequential transducer _i' = ⟨, λ_i', ο_i' ⟩, i∈{1,2}. Furthermore, the size of the automaton  is polynomial in the size of _1 and _2. 


Assume we are given two unambiguous transducers _1 and _2 with the input alphabet A and the output alphabet B. Since they are unambiguous, they have at most one accepting run on any input word. The idea is to construct a deterministic automaton whose language is the set of pairs of successful runs of _1 and _2 on words in their domain.

For convenience, we can assume that _1 and _2 have exactly one initial state each, denoted by i_1 and i_2. 
Let Δ_i, Q_i and F_i, i∈{1,2}, be the transitions, the set of states, and the set of final states of _i. 

The input alphabet of  is going to be A'=Δ_1 ×Δ_2.  The deterministic automaton  has the set of states Q_1× Q_2, initial state (i_1,i_2), set of final states F_1× F_2, and the set of transitions (denoted as Δ) of the form ((p,q), (δ,χ), (p',q')) such that δ∈Δ_1,χ∈Δ_2 are of the form (p,a,p') and
(q,a,q') for some letter a∈ A. It is easy to verify that the language accepted by ,  denoted as L' ⊆ (Δ_1 ×Δ_2)^*,  is the language
of all sequences of pairs of the form ρ=(δ_1,χ_1) ⋯ (δ_k,χ_k), k≥ 1 and δ_i ∈Δ_1, χ_i ∈Δ_2 for each 1 ≤ i≤ k, such that


  * δ_i and χ_i are transitions on the same letter,

  * δ_1 ⋯δ_k (denoted as π_1(ρ)) is a successful run of _1,

  * χ_1 ⋯χ_k (denoted as π_2(ρ)) is a successful run of _2.


Let λ_i:Δ_i → B^*, ο_i:F_i → B^*, i∈{1,2}, be the output functions of _i. We define λ_1':Δ→ B^* and λ_2':Δ→ B^* as follows: If Δ∋ψ = ((p,q),(δ,χ)(p',q')), we let λ_1'(ψ) = λ_1(δ) and λ_2'(ψ) = λ_2(χ). Similarly, we define ο_1',ο_2':F_1× F_2 → B^* as ο_1'(p,q) = ο_1(p) and ο_2'(p,q) = ο_2(q), for each (p,q) ∈ F_1× F_2. 

We take _1' and _2' to be the automaton  with the output functions λ_1',ο_1' and λ_2', ο_2' respectively. Clearly, they are of polynomial size w.r.t. _1 and _2. It is easy to show that there is a correspondence (↦) between L and L', namely L ∋ w ↦ρ∈ L' such that π_1(ρ) and π_2(ρ) are the unique successful runs of _1 and _2 on w respectively. Moreover, if w↦ρ then _1(w) = _1'(ρ) and _2(w) = _2'(ρ) (⋆).

It remains to show that d(_1,_2) = d(_1',_2'). Using (⋆) above, we observe that d(_1(w),_2(w)) = d(_1'(ρ),_2'(ρ)) such that w∈ L, ρ∈ L' and w ↦ρ. Since ↦ is a correspondence, we conclude that  d(_1,_2) = d(_1',_2'). 


Using the above result, the closeness w.r.t. the length metric  can be characterised in terms of delay as follows.

Consider the sequential transducers _1, _2 defined by the DFA  and output functions λ_1,ο_1 and λ_2,ο_2 respectively. The following are equivalent.


  * (_1,_2) is finite.

  * There is k∈ such that on any w∈ L(), the difference in lengths of the partial outputs of _1, _2 on any prefix of w is bounded by k.



(2)  (1) is obvious. 
For (1)  (2), WLOG assume that automaton  is trimmed, i.e., all states are accessible (reachable from the initial state) and coaccessible (from each state there is a path to some final state). Let ℓ be the maximum difference in the output lengths on any single transition, and n be the number of states of .  We claim that, if the difference in output lengths of the transducers on any input is bounded, then k = n ℓ validates our proposition.  Note that, the difference in the output lengths on any partial input u is at most |u|ℓ and we show that this does not exceed k. Suppose |u|ℓ > k = n ℓ, then |u| > n, and hence there is a state that is repeated on u such that the repeated part has nonzero difference in the output lengths. That is, u = u_1u_2u_3, with u_2 ≠ϵ such that the states reached after u_1 and that reached after u_1u_2 are the same, say q, and |λ_1(ρ)| - |λ_2(ρ)| ≠ 0, where ρ is the unique partial run from q on u_2. If w = uv for some w ∈ L() then u_1u_2^iu_3v ∈ L() for all i, and the difference in the output lengths become unbounded with increasing i. This contradicts that (_1,_2) is finite. Therefore, the difference in the partial outputs of _1, _2 on any prefix of w is bounded by k = n ℓ.





Given two transductions  and  we define a distance function which maps each word w to the  distance between their outputs on w.

	The distance function d :A^*→∪{∞} of  and  is  
	
    d (w) =  d((w),(w))
    		    if w∈() ∩()
    ∞    otherwise



Transducers  and  are close w.r.t. a metric d if their domains are the same and their distance function d is limited (i.e.,<∞ on its domain). Similarly k-closeness w.r.t. d of  and  reduces to k-limitedness of d. Limitedness problems are well-studied in the context of weighted automata <cit.>. Therefore, when the distance function d is computable by a (min, +)-automaton, the distance between  and  is computable due to <Ref>. 


However, there are distance functions that are not computable by weighted automata. Let A={a,b}. Consider the sequential transducers _1,_2:A^*→ A^* with the domain a^*b^* defining the functions a^pb^q↦ a^p, a^pb^q↦ a^q respectively (_1 outputs the a's and erases the b's, _2 erases a's and renames the b's as a's). It is easily checked that their distance function w.r.t. the Levenshtein family (d ∈{d_l,,}) is _1_2d : a^pb^q ↦ |p-q|.  

If f:A^*→∪{∞} is a function computed by weighted automata ((min, +) or (max,+) or B-automata <cit.>), then L_f≤ k = { w∈ A^* | f(w) ≤ k} is regular for each k≤. Hence the function _1_2d is not realised by any of them (consider the language L__1_2d≤ k). In fact, it can be shown that the function _1_2d is not computed even upto boundedness <cit.>. 

To compute k-closeness w.r.t. any of the edit distances, it is not necessary to compute the distance function precisely.  The k-approximation of the distance function d is the function d k : w ↦ d(w) if d(w) ≤ k and ∞ otherwise. 

If  and  are close w.r.t. the length metric, then the approximation d k for a metric d ∈{d_l,,,d_h,d_t,d_c} is computed by a distance automaton for each k ∈.



Let _1 and _2 be two transducers. The domains of these transducers are identical since they are close w.r.t. the length metric. Hence, we can construct _1 = ⟨, λ_1, ο_1 ⟩ and _2 = ⟨, λ_2, ο_2 ⟩ with domain L (by virtue of <Ref>).
Since the transducers  _1 and _2 are close w.r.t. the length metric, by virtue of <Ref>, there is a maximum delay ∂∈ℕ between any partial outputs of  and  on any input.

For all metrics d∈{d_l,d_h,d_t,,}, fix a set of edits C supported in the metric.  We construct a distance automaton _C,k — weighted automaton over the semiring (ℕ,min,+, ∞,0) —  that reads an input word w and accepts it if we can perform at most k edits in C to _1(w) and obtain _2(w).  The cost of a run is the number of edits that it uses. For this the states of automaton _C,k are those of  augmented with a budget b and unmatched leftover word of the form  (u, ϵ) or (ϵ, u) with |u|≤𝑚𝑎𝑥(∂,k). Initially, the budget is k, and the word is (ϵ, ϵ).  While performing a transition δ of , from a state annotated with b and (ϵ, u), the automaton _C,k nondeterministically performs b' edits from C so as to partially match (λ_1(δ), uλ_2(δ)). It then moves on to the target state with the reduced budget b-b' and the updated leftover word.  The cost of the transition is the number of edits used in the transition, i.e., b'. It is easy to verify that _C,k exactly computes _1_2dk. 

For conjugacy distance, we construct a new distance automaton _k that remembers a prefix of length at most k of the output of the first (or second) transducer and matches the shifted output with the remaining output of the transducer. The cost of a run is the length of the prefix, i.e., the number of cyclic shifts required to match the outputs.  
 For this, the states of automaton _k are those of  augmented with a word of the form (u, v) with ||u| - |v|| ≤∂, and  either |u|≤ k or |v| ≤ k . Here, u (resp. v) is a suitable candidate for the prefix of the output of the first (resp. second) transducer to be matched with the suffix of the output of the second (resp. first) transducer. Initially the word is (ϵ, ϵ). While performing a transition δ of , from a state annotated with (u,v), the automaton _k either choose to perform step 1 (stores the output of first and second transducer of at most k length), or until nondeterministically chooses to perform step 2 where it starts matching the output of first and second transducer and finally check if the stored output matches with the remaining output.


  * Go the the target state with updated word as (u', v') = (uλ_1(δ), vλ_2(δ)) only if ||u'| - |v'|| ≤∂, and |u'| ≤ k or |v'| ≤ k with the cost of the transition being zero. 

  * There are two symmetric cases. Start to partially match the output of the first (resp. second) transducer uλ_1(δ) (resp. vλ_2(δ)) with that of the upcoming output of the second  (resp. first) transducer, i.e., λ_2(δ) (resp.  λ_1(δ)) only if |v| ≤ k (resp. |u| ≤ k). It then moves on to the target state with updated word (ϵ,v) (resp. (u,ϵ)) and also the leftover word obtained after matching uλ_1(δ) and λ_2(δ) (resp. vλ_2(δ) and λ_1(δ)). The cost of the transition is set to be |v| (resp. |u|). For the upcoming transitions on , the matching continues until the output of the second (resp. first) transducer is exhausted with cost of transitions being zero. While matching, the state may need to additionally store the leftover words of the form (w, ϵ) or (ϵ, w). After that, it checks if the stored word v (resp. u) matches the first (resp. second) transducer's remaining output. 


Note that the size of _C,k and _k is exponential in k (as it has to keep track of the unprocessed words).


To check if  and  are k-close, we check if they have the same domain and they are close w.r.t. the length metric (otherwise they are neither close nor k-close). If so, we check if the domain of T is same as the domain of d k. Thus we get:

	Let d be any metric from Table <ref>, and    and  be any functional transducers.  It is decidable if  and  are  k-close w.r.t. d.  



 Interestingly, as elaborated in <Ref>,  for Hamming and transposition distances we have direct procedures for k-closeness that does not involve the weighted automata. 



 §.§ Diameter of a Rational Relation
 



The diameter of a rational relation R with respect to a distance d, denoted by Rd, is the supremum of the distance of the related words in R.

    Rd = sup{   d(u,v)  |  (u,v) ∈ R  }


Similar to the questions asked in Table <ref>, we can ask the questions given in Table <ref> about diameter of a rational w.r.t. a metric d.

We say a rational relation has bounded (resp. k-bounded) diameter w.r.t. a distance d if the diameter of the relation w.r.t. d is finite (resp. ≤ k).
A rational relation with bounded delay are precisely those relations with bounded diameter w.r.t. a length metric. Relations with 0-delay are called length-preserving relations <cit.>  where any two related words are of equal length. It is decidable to check if a rational relation has bounded delay or 0-delay <cit.>.

Relations bounded w.r.t. the discrete metric are simply those with only identical pairs. It is decidable to determine if a rational relation R is identity. First, check if R is length-preserving. If so, we can construct a letter-to-letter transducer for R based on Eilenberg and Schützenberger's theorem <cit.> stating that a length-preserving rational relation over A^* × B^* is a rational subset of (A × B)^*, or equivalently, it can be realised by a letter-to-letter transducer whose transitions are labelled with elements of A × B.  Finally, validate this transducer for identity by examining the labels of each transition.



 §.§ Index of a Rational Relation in a Composition Closure



Consider two rational relations R over A^* × B^* and S over B^* × C^*. The composition S ∘ R over A^* × C^* is defined by
(S ∘ R)(u) = S(R(u)) = ⋃_v ∈ R(u) S(v).

Let S be a rational relation over A^* × A^*. Let S^ n denote the composition of S with itself n≥ 0 times (S^ 0 is taken to be the identity relation), and let S^≤ n denotes the composition of S with itself at most n times, i.e., S^≤ n =  S^ 0∪ S^ 1∪⋯ S^ n. 


The composition closure of S, denoted as S^ *, is defined as
S^ * = ⋃_i ≥ 0 S^ i. 

Notice that we use parenthesis around the superscript to indicate that the base operation is composition, and not concatenation.

Let S be a rational relation over A^* × A^*. An index of a rational relation R in the composition closure of S, denoted as RS, is the smallest integer k such that R is contained in S^≤ k. 



Consider a relation S over {a,b}^* ×{a,b}^* that deletes the first a if exists on any input. Fix an integer k > 0 and let R be the relation that deletes the first k a's from the input if exists. The index of R in S^ * is k since for any input word u ∈ A^*, R(u) ∈ S^≤ k(u).  

Consider another relation R^' that deletes all a's from the input. Since R^'(a^k+1) ∉S^≤ k(a^k+1)  for any k >0, the index of R^' in S^ * is ∞.


As seen in the case of the distance and diameter problem, we can ask questions in Table <ref> about the index of a rational relation in the composition closure of a relation.

We say a rational relation R has bounded (resp. k-bounded) index  in the composition closure of a rational relation S if the index of R in S^ * is finite (resp. ≤ k). 


The following lemma shows that checking the boundedness of the index problem for an arbitrary rational relation is difficult. 

It is undecidable to check if a rational relation has a bounded index in the composition closure of an arbitrary rational relation.



Proof by reducing a version of the halting problem of the Turing machine to the bounded index problem of a rational relation. 

A Turing machine is a  mathematical model of computation consisting of 7-tuple M = ⟨ Q,Σ,Γ,δ,q_in,q_accept,q_reject⟩ where Q is a finite set of states; q_in, q_accept, q_reject∈ Q is the start state, accept state and reject state respectively; Σ,Γ are the finite input and tape alphabet respectively; and δ is the transition function, δ: Q ∖{q_accept,q_reject}×Γ→ Q ×Γ×{L,R} — given a state and the current tape symbol (pointed by the tape head) the transition writes a new symbol, changes state and moves the tape-head one cell either to the left or to the right. A configuration of a Turing Machine is a snapshot of the current state of the machine. It can be expressed as a word consisting of three components: the tape contents to the left of the tape head, the current state, and the tape contents to the right of the tape head (including the current cell). For example, configuration x_1x_2 ⋯ x_n q y_1y_2 ⋯ y_m, where x_i,y_i ∈Γ, indicates that tape content is x_1 ⋯ x_ny_1 ⋯ y_m followed by infinite blanks, the tape head is pointing at y_1 and the current state is q. On an input word w, the initial configuration is q_in w, and a configuration of the form xq_accept y and x q_reject y, x,y ∈Γ^*, are called the accepting and rejecting configuration respectively. Let ⊢ represent a relation between two configurations C_1,C_2 such that C_1 ⊢ C_2 only if C_2 is a possible next valid configuration. For instance, for a transition δ(q,a) = (q^',b,L) and current configuration xqay, where x,y ∈Γ^*, a ∈Γ, a next valid configuration would be xbq^' y. Hence xqay ⊢ xbq^' y. It is easy to verify that ⊢ is a rational relation. A computation on a Turing Machine is a sequence of configurations C_0, C_1 ⋯ C_m where each configurtion is obtained from the previous one by the relation ⊢, i.e.,
C_i-1⊢ C_i   ∀ 1 ≤ i ≤ m
and C_0 is the initial configuration. If the final configuration, i.e., C_m, is accepting then the word is accepted by the machine (accepting computation). If instead C_m is rejecting then the word is rejected by the machine (rejecting computation). There can be computations where the input word is neither accepted nor rejected and the Turing machine runs forever.


Reduction: First we recall a version of the halting problem for Turing machines.

Input: a Turing machine M and an input word x

Output: Yes, if M halts on x and erases the tape contents; No, otherwise.

Given input M and x, let q_in and q_accept be the initial and accepting state of M respectively. We can define a singleton relation R= {(q_in x, q_accept)}. Let S be the ⊢ relation over configurations of M. Both R and S are rational relations.

R has a bounded index in S^* if and only if there exists some k > 0 such that q_accept∈ ⊢^k (q_inx). This is equivalent to saying that R has a bounded index in S^* if and only if M halts on x and erases the tape contents. Since the halting problem for the Turing machine is undecidable, we can conclude that it is undecidable to check if a rational relation has a bounded index in the composition closure of a rational relation.


However, we show that the index problem is decidable w.r.t. a large class of rational relations defined below.



Let S be a rational relation over A^* × A^*. Let d_S: A^* × A^* →∪{∞} be the distance between two vertices in the graph of S, i.e., for any two words u and v, d_S(u,v) is the smallest i such that v ∈ S^ i(u), and ∞ otherwise.

We say S is a d-metrizable relation for a metric d if d_S ≈ d. 



Let R be a rational relation and S be a d-metrizable relation for an integer-valued metric d for which ≲ d. If boundedness of diameter w.r.t. d is decidable for a rational relation, then RS is computable.



Similar to distance problem, the index problem is computable iff bounded index and k-bounded index problem are decidable. 
For a rational relation R and d-metrizable relation S, we show that RS < ∞ iff Rd < ∞ as follows.

    Rd < ∞   ∃ k∈ℕ s.t. ∀ (u,v) ∈ R, d(u,v) ≤ k
       ∃ k' ∈ℕ s.t. ∀ (u,v)∈ R, d_S(u,v) ≤ k'       (Since d_S ≈ d)
       ∀ (u,v)∈ R, v ∈ S^≤k'(u)       (Definition of d_S)
       RS < ∞


Therefore, if the boundedness of diameter w.r.t. d is decidable for a rational relation, then we can decide if RS < ∞. If so, then it suffices to decide if RS≤ k for k =0, 1, … and output the smallest k as the index of R in the composition closure of S. 

Since Rd < ∞ and ≲ d, the rational relation R has a bounded delay. Similarly, S also has a bounded delay since for all (u,v) ∈ S, d_S(u,v) = 1 ∃ k ∈ℕ s.t. d(u,v) ≤ k (since d_S ≈ d) ∃ k' ∈ℕ s.t. (u,v) ≤ k' (since ≲ d). Since S has bounded delay, for any k ∈ℕ, S^ k also has bounded delay.  It is known that emptinesss  and set difference of two rational relations with bounded delay is decidable (Corollary 2 of <cit.>). For any k ∈ℕ, deciding RS≤ k reduces to checking if R ⊆ S^ k (or equivalently, R ∖ S^ k = ∅), and hence decidable.

A close and (almost) dual notion is that of a metric that defines a rational relation.

A distance d on words is rationalizable if the relation S_d={(u,v) | d(u,v)=1}, called the distance relation of d, is rational. 



Consider the hamming distance d_h. We can construct a rational relation S_h = {(u,v) | u  and  v  differ only in exactly one position}.  For example, let A={a,b} and S_h(aba) = {bba,aaa,abb}. For this, construct a transducer that nondeterministically chooses a position and replaces the input letter with other letters in the alphabet.  Similarly, 
the distance relation of the length metric S_len = { (u,v) | ||u| - |v|| =1} is also rational.

In fact, we have the following result about the rationalizability of edit distances referred in Table <ref>.


Every edit distance d∈{d_l,d_h,d_t,d_c,,} is rationalizable.


Let d be an edit distance. Let C be the set of permissible edits in d. We can construct a rational relation S such that S = {(u,v) | d(u,v) = 1}. For d ∈{d_l,d_h,d_t,,}, we can construct a transducer that nondeterministically chooses a position and an edit from set C and applies that edit to the chosen position. For example, the rational relation S_l over A^* × A^* for Levenshtein edit distance is as follows. For all, u,v ∈ A^*, (u,v) ∈ S_l if and only if there exists x,y ∈ A^*, a,b ∈ A with a ≠ b, such that either one of the following is true.


  * u=xy, v=xay (insertion)

  * u=xay, v=xy (deletion)

  * u = xay, v=xby (substitution)

For conjugacy distance, S_c = {(u,v) |either u=ax and v=xa, or u=xa and v=av, x ∈ A^*, a∈ A}. For this, we can construct a transducer that nondeterministically remembers (or guesses) the first (or last) letter of the input word and output it at the end (or beginning) along with the rest of the input word. 

 


 §.§ Reductions between Distance, Diameter and Index Problems


We show that the distance problem of two rational functions is mutually reducible to the diameter problem of a rational relation, which in turn is mutually reducible to the index problem of a rational relation in the composition closure of a rationalizable distance. Thus, their closeness and boundedness problems are also interreducible.


The correspondence between distance and diameter follows from Nivat's theorem:
 (<cit.>) 
Let A and B be alphabets. The following conditions are equivalent.


  * R is a rational relation over A^* × B^*.

  * There exist an alphabet C, two alphabetic morphisms ϕ : C^* → A^* and ψ : C^* → B^* and a regular language L ⊂ C^* such that R = {(ϕ(w),ψ(w)) | w ∈ L}


From <Ref> and (2)  (1) in the above theorem, it follows that distance of two rational functions reduces to the diameter of a rational relation. Now, given a rational relation R, we can create two functional transducers _1 and _2 in the following way. The domain for these transducers corresponds to the set L in <Ref>. For each transition in _1 and _2 that involves an input alphabet symbol σ, we set the outputs to be ϕ(σ) and ψ(σ) in <Ref>, respectively. Consequently, _1 and _2 consist of the sets {ϕ(w) | w ∈ L} and {ψ(w) | w ∈ L} respectively. Since the domain of these transducers is identical, the distance between _1 and _2 with respect to any distance d, 
d(_1,_2) =  sup{   d(ϕ(w),ψ(w))  |  w ∈ L  },
 that is equivalent to the diameter of R w.r.t. the distance d.

The correspondence between diameter and  index  for rationalizable distances is stated in the following proposition.

The diameter of a rational relation R w.r.t. a rationalizable distance d is equal to the index of the rational relation R in the compostion closure of the distance relation of d.



Assume that the diameter of a relation R w.r.t. a distance d is ∞. We claim that the index of R in S_d^ * is also ∞ where S_d is the distance relation of d. Suppose not, i.e., let k<∞ be the index of R in S_d^ *. Thus, ∀ (u,v)∈ R, v∈ S_d^≤ k(u). Since S_d is the distance relation of d, ∀ (u,v)∈ R, d(u,v)≤ k. However, this contradicts the fact that Rd=∞. Hence, the index of R in S_d^ * is infinite. Similarly, we can prove the other direction. 
Now, suppose the diameter of R w.r.t. d is finite, i.e.,

    diameter of R w.r.t. d is k < ∞   ∀ (u,v) ∈ R, d(u,v) ≤ k
       ∀ (u,v)∈ R, v ∈ S_d^≤ k(u)
        index of R in S_d^ * is k.






 §.§ Decidability Results

We study the problems stated in Tables <ref>, <ref> and <ref> and show that they are decidable for the metrics in Table <ref>. The index problems stated in Table <ref> are undecidable in general (see <Ref>), but is decidable for d-metrizable relations for metrics d given in Table <ref>.

Recall that, w.r.t. a metric d, distance problem is computable if and only if both closeness and k-closeness are decidable (see <Ref>). We have shown that the k-closeness is decidable for all the metrics in Table <ref> (<Ref>). Hence to show the decidability of all the problems in Table <ref>, it suffices to show the decidability of the closeness problem. Furthermore, thanks to the inter-reductions described above (see <Ref>), the decidability of Table <ref> follows as well as the decidability for the problems in Table <ref> for the rationalizable distance. Moreover, the index of a rational relation in the composition closure of a d-metrizable relation for a metric d given in Table <ref> is computable by <Ref>.

It only remains to prove that closeness is decidable for edit distances in Table <ref>. This is stated below, and proved in the following section.


Let d be any metric from Table <ref>, and   and  be any functional transducers.  It is decidable if  and  are  close w.r.t. d.  




§ CLOSENESS FOR EDIT DISTANCES



In this section we show that closeness is decidable for all the edit distances in Table <ref>. The first step is to check if the domain of the transducers are the same. This reduces to checking the equivalence of the underlying automata. For sequential transducers, the underlying automaton is a DFA, while for unambiguous transducers, the underlying automaton is an unambiguous NFA. Checking the equivalence of two unambiguous automata can be done in polynomial time <cit.>, while it is PSPACE in the case of ambiguous automata <cit.>.  Therefore, from now on, we assume that the domains of the transducers given as input to the closeness problem are identical.


<Ref> allows us to state the distance and closeness problems more abstractly in terms of an automaton over pairs of words. The proposition asserts that distance and closeness problems of two given sequential or unambiguous transducers _1 and _2 can be reduced to the corresponding problem for a DFA  with two sets of output functions λ_1,ο_1 and λ_2,ο_2. We can combine the output functions to output a pair of words. That is to say, let λ:Δ→ B^*× B^* be defined as λ(δ) = (λ_1(δ),λ_2(δ)), where δ∈Δ and Δ is the set of transitions of . Similarly let  ο(p) = (ο_1(p),ο_2(p)), where p ∈ F and F is the set of accepting states of . Henceforth, we can assume that we are given a DFA  with the output functions λ and ο, denoted as the sequential transducer . Since the input words are inconsequential for computing the distance, we can convert the transducer  to an automaton  that accepts a set of pairs of output words over B^* × B^*, i.e., L() = {(u,v) ∈ B^* × B^* | (u,v) = (w), w ∈()}. Clearly, transducers _1 and _2 are close w.r.t. d if and only if there exist an integer k ≥ 0 such that ∀ (u,v) ∈ L(), d(u,v) ≤ k. 

Conjugacy of words plays an important role in closeness problems. A pair of words (u,v) is conjugate if there exist words x and y (possibly empty) such that u=xy  and v=yx or equivalently, u and v are cyclic shifts of one another. For example, ( 𝑎𝑎𝑎𝑏, 𝑎𝑎𝑏𝑎) is a conjugate pair where x=a and y=aab. Conjugacy relation is an equivalence relation on the set of words. A set of pairs is conjugate if each pair in the set is conjugate.



Let _1 and _2 be two sequential transducers that define a function from A^* to B^*. If _1 and _2 are close w.r.t. a metric d∈{d_l,d_h,d_t,d_c,,}, then every loop in the trim automaton over B^* × B^*, that accepts set of all pairs of output words of _1 and _2 on any input, generates only conjugate pair of words.


 This proof is an adaptation of a related result in <cit.>. 
Let  be a trim automaton that realises the pair of output words of transducers _1 and _2 on any input. Since _1 and _2 are close w.r.t. d, there exist an integer k ≥ 0 such that ∀ (u,v) ∈ L(), d(u,v) ≤ k.  Let (u,v) be a pair labelled in a loop rooted at some state q. Hence (u^ℓ,v^ℓ) for each ℓ≥ 0 is also a pair in a loop rooted at q. We can safely assume that |u| = |v|, otherwise the edit distance will be unbounded as each iteration will increase the edit distance by a difference in length of u and v  (<Ref> of <Ref>). 

Since  is trimmed, there exists a path from an initial state q_0 to q and from q to a final state q_f. Let (_0,_0) be a pair labelled in a path from q_0 to q, and let (_1,_1) be a pair labelled in a path from q to q_f. Thus, pair (_0,_0)(u^ℓ,v^ℓ)(_1,_1) belongs to L() where ℓ = 2^k (some value much larger than k). Since ℓ is much larger than k and d(_0u^ℓ_1,_0v^ℓ_1) ≤ k, there exist large portions of u's and v's that match. Therefore, we can infer that u is a factor of vv, and v is a factor of uu.


Since v is an infix of uu, the following holds as shown in <Ref>. There exist words x,y,p and q such that v = xy and u = px = yq. 
Since |u| = |v|, length of p and length of y are the same, that implies p=y (since u = px = yq). Therefore, u = yx. Hence u and v are conjugate words. Since the pair (u,v) was arbitrary, any pair generated by a loop in  is conjugate.




 §.§ Closeness w.r.t. Levenshtein distances and Conjugacy

In this subsection, we decide closeness w.r.t. Levenshtein family of distances — Levenshtein, Damerau-Levenshtein, and LCS distances — and conjugacy distance. Levenshtein family of distances are all equivalent with respect to closeness problems by <Ref> and <Ref>.

We have already seen that given two unambiguous transducers _1 and _2 with identical domains, there exists an automaton  over B^* × B^* that accepts a set of all pairs of output words of _1 and _2 on any input. Thus, we can state the distance and closeness problems in terms of rational expressions over B^* × B^*.

We define pairs over the alphabet B to be the set B^* × B^* with the pointwise concatenation (u,v) · (u',v') = (u· u', v · v'). 
A rational expression of pairs over the alphabet B is a rational expression over the alphabet {(b,b') | b,b' ∈B ∪{ϵ}} that generates subset of pairs over B.

From the automaton  over B^* × B^*,  using state elimination method (<cit.>, Lecture 9), we can construct the rational expression of pairs E  for the output pairs generated by the transducer _1 and _2 on any input. 
We can lift the metric d to expressions by letting d(E) = sup{d(u,v) | (u,v) ∈ L(E)}.
Clearly d(E) = d(_1,_2). Thus, the distance and closeness problems of sequential and unambiguous transducers reduce to the corresponding problems for a rational expression of pairs. Henceforth we assume that we are given a rational expression of pairs. 

In the context of conjugacy distance, the closeness of a rational expression necessarily implies that every pair in the expression is conjugate. Otherwise, if there exists a pair (u,v) ∈ L(E) such that u is not conjugate to v, then d_c(u,v) = ∞, thus d_c(E) = ∞. In fact, this is also a sufficient condtion. The proof relies on the results from <cit.> that studies the conjugacy of rational expression over pairs of words. 
It crucially uses the notion of a common witness of a set of pairs.

 A witness of  pair of conjugate words (u,v) is a word z such that either uz = zv (called an inner witness) or zu = vz (called an outer witness). A common witness of a set of pairs is a word z such that either z is an inner witness of every pair in the set, or z is an outer witness of every pair in the set.

Lyndon and Schützenberger in 1962 gave a characterisation of conjugacy of a pair of words, stated as a pair of words is conjugate if and only if it has both inner and outer witness (Proposition 1.3.4 of <cit.>). In <cit.>, it is generalised to a set of pairs as follows.
 (<cit.>)
Let M = (α_0,β_0) G_1^* (α_1,β_1) ⋯ G_k^*(α_k,β_k) be a set of pairs where G_1, …, G_k, k > 0 are arbitrary sets of pairs of words, and (α_0,β_0), …, (α_k,β_k) are arbitrary pairs of words. The set M is conjugate iff M has a common witness.

Existence of a common witness bounds the conjugacy distance of an expression as follows.

If a rational expression over pairs E has a common witness z, then d_c(E) ≤ |z|.



Since E has a common witness, either ∀ (u,v) ∈ L(E), uz = zv, or ∀ (u,v) ∈ L(E), zu = vz. WLOG, assume that  ∀ (u,v) ∈ L(E), uz = zv. Now, for any pair (u,v) ∈ L(E):


  * If |u| > |z|, then z is a prefix of u and suffix of v and hence (u,v) = (zp,pz) for some word p ∈ A^*. Therefore d_c(u,v) ≤ |z| since v can be  obtained by |z| left cyclic shifts of u.

  * Otherwise, when |u| ≤ |z|, the number of cyclic shifts required to transform u to v (note that u and v are conjugate since they have a witness) is less than |u| ≤ |z|. 

A rational expression is sumfree if it does not use sum (i.e., +). In <cit.>, it is shown that if  a common witness exists, it is computable 
for a sumfree rational expression over pairs of words.
It is folklore that every rational expression is equivalent to a sum of sumfree expressions <cit.>. 
The proposition below implies that to show closeness for a sum of sumfree expressions, it suffices to show closeness for each of its constituent sumfree expressions. 

Let E = E_1 + ⋯ + E_k, k≥ 1 be a rational expression of pairs. Then d(E) =  max (d(E_1), …, d(E_k)) for all word metrics d.


It suffices to show that if E=E_1+E_2, then d(E) = max(d(E_1),d(E_2)). Since L(E_i) ⊆ L(E), i ∈{1,2}, we can deduce that d(E_i) ≤ d(E) and hence max(d(E_1),d(E_2)) ≤ d(E). It remains to show that d(E) ≤max(d(E_1),d(E_2)). We have two cases.


  * If d(E) = k ∈, then for each pair in E the distance is at most k, and there is a pair (u,v) ∈ L(E) with distance k. Then, for each pair in E_1 as well as E_2 the distance is at most k, and the expression that contains the pair (u,v) has distance k. 


  * If d(E) = ∞, then either there is a pair (u,v) with distance ∞, in which case one of d(E_1),d(E_2) is ∞. Otherwise, there is an infinite subset of pairs L ⊆ L(E) such that for each k ∈ N there is a pair with distance at least k. Since L is infinite, one of L ∩ L(E_1), L ∩ L(E_2) is infinite, and the corresponding expression has distance ∞. 

An expression is conjugate, if every pair generated by the expression is conjugate. The following proposition characterises closeness w.r.t. conjugacy distance.


A rational expression over pairs of words is close w.r.t. conjugacy distance if and only if the expression is conjugate. Furthermore, the closeness w.r.t. conjugacy distance is decidable.



One direction is trivial. Assume E to be an arbitrary rational expression of pairs and is conjugate. Let E = E_1 + E_2 +⋯ + E_k where E_1,E_2, …, E_k are sumfree expressions. Since E is conjugate, each of its sumfree constituent E_i for 1 ≤ i ≤ k is also conjugate. Using <Ref>, each E_i has a common witness, say z_i. From <Ref>, d_c(E_i) ≤ z_i. Therefore, d_c(E) is close w.r.t. conjugacy distance by <Ref>. Hence, to decide closeness of E w.r.t. conjugacy distance, it suffices to check if E is conjugate. This reduces to checking if a common witness exists for each sumfree constituents. It is shown to decidable in <cit.>.


Now consider the case of Levenshtein distances. From <Ref>, if an expression is close w.r.t. Levenshtein distances, it is necessary that every pair generated by a Kleene star in the expression needs to be conjugate. Using common witness, we show that it is also a sufficient condition.

If a rational expression of pairs E has a common witness z, then d_l(E) ≤ 2|z|.



The proof is similar to <Ref>. Since E has a common witness, either ∀ (u,v) ∈ L(E), uz = zv, or ∀ (u,v) ∈ L(E), zu = vz. WLOG, assume that  ∀ (u,v) ∈ L(E), uz = zv. For any pair (u,v) ∈ L(E), |u| = |v| since uz = zv. There are two cases, either |u| > |z| or |u| ≤ |z|. If |u| > |z|, then z is a prefix of u and suffix of v and hence (u,v) = (zp,pz) for some word p. Therefore, d_l(E) ≤ 2|z| by deleting z in the beginning and insert z at the end of u. Suppose |u| ≤ |z|, the number of edits required to transform u to v is less than |u| + |v| ≤ 2|u| ≤ 2|z|.



Closeness of a rational expression w.r.t. Levenshtein distance is decidable.



Given an arbitrary rational expression, there is an equivalent sum of sumfree expression. From <Ref>, to show closeness for a sum of sumfree expressions, it suffices to show closeness for each of its constituent sumfree expressions. The general form of a sumfree expression E = (α_0,β_0) E_1^*(α_1,β_1) ⋯ E_k^*(α_k,β_k) where k ∈ℕ, for 0 ≤ j ≤ k, (_j,_j) is a (possibly empty) pair of words, and for each 1 ≤ i ≤ k, E_i is a sumfree expression.


A sumfree expression E = (α_0,β_0) E_1^*(α_1,β_1) ⋯ E_k^*(α_k,β_k) is close w.r.t. Levenshtein distance if and only if each E_i^* for 1 ≤ i ≤ k is conjugate.



From <Ref>, if E is close w.r.t. Levenshtein edit distance then each E_i^* is conjugate. For the other direction, if each E_i^* is conjugate, then each E_i^* has a common witness, say z_i, by <Ref>. From <Ref>, d_l(E_i^*) ≤ 2|z_i|. Further, d_l(E) ≤∑_j ∈{0 … k}d_l(_j,_j) + ∑_i ∈{1 … k}d_l(E_i^*) = ∑_j ∈{0 … k}d_l(_j,_j) + 2∑_i ∈{1 … k}z_i, hence finite. This implies that if each E_i^* in E is conjugate, then d_l(E) is finite.

Therefore, checking the closeness of a rational expression w.r.t. Levenshtein distances reduces to checking the existence of a common witness of each Kleene star in its sumfree constitutents, and thus decidable.

For a sumfree rational expression, a witness, if exists, can be computed in polynomial time <cit.>, and thus closeness w.r.t. Levenshtein and conjugacy distances are decidable in polynomial time. However, converting a rational expression to a sum of sumfree rational expressions can cause an exponential blow-up both in the number of summands and the size of each summand  <cit.>.  




 §.§ Closeness w.r.t. Hamming and Transposition distances


Closeness w.r.t. Hamming and Transposition distance are decidable for functional transducers.


Given two functional transducers, check if their domains are the same. If not, the distance is ∞ hence they are not close. 
Assume they have an identical domain. By <Ref>, it suffices to consider two sequential transducers with a common underlying DFA. Let _1 = ⟨, λ_1, ο_1⟩ and _2 = ⟨, λ_2, ο_2⟩ be two sequential transducers. WLOG, we make the following assumptions.



  * (Property ⋆) Automaton  is trimmed, i.e., all states are accessible (reachable from the initial state) and coaccessible (from each state there is a path to some final state).


  * (Property ) _1 and _2 produce output words of identical length: otherwise the Hamming as well as transposition distance will be ∞. We can check this property: rename all the output letters in _1 and _2 to a and check their equivalence.

  * The delay between partial outputs of _1 and _2 is at most k ∈ (By <Ref>).

 

Let Q and F⊆ Q be the set of states and final states of  respectively, and let q_0∈ Q be the initial state. For states p,q ∈ Q, Let M_p,q be the set of pairs (u,v) such that there is a run ρ from p to q and u = λ_1(ρ) and v=λ_2(ρ). Extending this notation, for a state q_f ∈ F, let M'_q,q_f be the set of pairs (u,v) such that u = u'·ο_1(q_f), v = v' ·ο_2(q_f) and (u',v')∈ M_q,q_f.


Let q be a state of the automaton. If (α,β) and (α',β') are two pairs in  M_q_0,q, then 
|α|-|β| = |α'|-|β'|, or else one of the pairs in { (αα”, ββ”),  (α'α”, β'β”)} will have different lengths, where (α”,β”) is some pair in M_q,q_f, for some q_f ∈ F,  guaranteed by Property (⋆). Therefore with each state q, we can associate the delay of a run reaching it, called the delay at q, denoted by ∂_q, as |α|-|β|. Clearly ∂_q ≤ k. 
By a symmetric argument, if (α,β) and (α',β') are two pairs in  M_q,q_f, where q_f is some final state, then |α|-|β| = |α'|-|β'| = -∂_q.
This also implies that for all (u,v) ∈ M_q,q, |u| = |v|.


For each state q, either M_q,q={(ϵ,ϵ)}, or M_q,q is infinite. Let q be a state for which M_q,q is nonempty.  For a delay ∂∈ℤ, a pair (u,v) ∈ M_q,q where n= |u| > ∂, we define the interior of the pair (u,v) as 

    _∂(u,v)   =  (u[1… n-∂],v[∂+1… n])    if ∂≥ 0
    
    (u[∂+1… n],v[1… n-∂])    if ∂ < 0

For example, _1(abc, def) = (ab,ef) and _-1(abc, def) = (bc,de). We also define the Left-Border and Right-Border of the pair (u,v) as

0.35

    _∂(u,v)    =  v[1…∂]    if ∂≥ 0
    
    			u[1…∂]    if ∂ < 0

 
0.6

    _∂(u,v)    =  u[n-∂+1… n]    if ∂≥ 0
    
    		v[n-∂+1… n]    if ∂ < 0





Hamming distance between _1 and _2 is unbounded if and only if there exists a state q∈ Q and (u,v) ∈ M_q,q such that |u|=|v| > ∂_q, and u' ≠ v' where (u',v')=_∂_q(u,v).



The <Ref> depicts the situation described by (2). 

(←): Assume there exists a state q∈ Q and (u,v) ∈ M_q,q such that |u|=|v| > ∂_q, and u' ≠ v' where (u',v')=_∂_q(u,v). Let (α_0,β_0)∈ M_q_0,q and (α_1,β_1)∈ M_q,q_f. Consider the pair (u_i = α_0u^iα_1, v_i = β_0v^iβ_1), i≥ 1 (shown in <Ref>). Since u'≠ v', we can deduce that d_h(u_i,v_i) ≥ i. Hence d_h(_1,_2) = ∞.



 


(→): Assume d_h(_1,_2) = ∞. Assume  has n states and the maximum length of an output produced on any transition or at the end-of-input is ℓ. Choose a run ρ of  such that the distance between the outputs produced on ρ = δ_1 ⋯δ_m, m>0 is at least ((k+2)n+1)ℓ. We can associate each edit in λ_1(ρ) with the transition δ_i such that the edit happens in λ_1(δ_i). Since there are 
((k+2)n+1)ℓ edits, there are at least (k+2)n+1 transitions in ρ whose output words are edited. 
Associate each transition with its source state. By pigeonhole principle, there is a state q such that ρ=ρ_1·ρ_2·ρ_3 where


  * ρ_1 is a run from the initial state q_0 to q,

  * ρ_2 is a run from q to itself,

  * ρ_3 is a run from q to a final state q_f, and

  * there are at least (k+1) edits in the factor λ_1(ρ_2).


Let u=λ_1(ρ_2) and v = λ_2(ρ_2). Clearly |u| = |v| and |u| ≥ (k+1). Since the edits in u are at least k+1, there is a position on which the pair _∂_q(u,v) differ.




    Deciding <Ref>:

For checking characterisation in <Ref>, for each state q for which M_q,q is nonempty, we need to check if the (q) = {_∂_q(u,v) | (u,v) ∈ M_q,q} consist of only identical pairs of words. Towards this, we assume that the transducers given are normalised, i.e., for any transition δ in , λ_i(δ) for i = {1,2} is either a single letter or ϵ.

We can verify and compute the unique delay, if exists, for each state in polynomial time. For this, set the delay at intial state to be zero. Now for each transition, compute the delay of the target state. If the delay of the target state is not yet computed, set this as its delay. On the other hand, if delay of target state is already computed, then check the computed delay is equal to that. If not, the delay is not unique and thus, Property (⋆) is not satisfied and transducers are not close. Otherwise continue with the next transition of  till all transitions are covered.


 We construct a forward and backward gadget for each state that unfolds the loop up to its delay in both directions trimming the  and  respectively. For a state q with the delay ∂_q, if ∂_q > 0, then the forward gadget of q will produce pairs {(u[1 ∂_q], ϵ) | (u,v) ∈ M_q,q, |u| > ∂_q}, and the backward gadget of q will produce pairs {( ϵ, v[(n-∂_q)  n) | (u,v) ∈ M_q,q, n=|v| > ∂_q}. Symmetrically for ∂_q <0.

Instead of constructing these gadgets for each state, we combine the construction for each strongly connected component (SCC). In polynomial time, we can find all the strongly connected components  (SCCs) of the automaton . Let S be the set of states in a SCC and ∂ be the maximum absolute value of delay among all the states in S. Construct a forward and backward gadget (or automaton) _S and _S respectively with states from S ×{-∂, -∂ +1 , …, 0, 1, 2 , …, ∂} with output functions λ_f_1,λ_f_2 and λ_b_1,λ_b_2 respectively. 

Initially, the forward gadget has states of the form (q,∂_q) for q ∈ S, and the backward gadget has states of the form (q,-∂_q)for q ∈ S . 

For a transition δ = (p,a,q) in  where a∈ A and p,q ∈ S,


  * In forward gadget, for each state (p,i) ∈_S, we add a transition δ_f = ((p,i), a,(q,j))  such that 


  * if i>0, then λ_f_1(δ_f) = λ_1(δ), λ_f_2(δ_f) = ϵ, and if  λ_2(δ) ≠ϵ then j=i-1; else j=i.

  * if i<0, then λ_f_1(δ_f) = ϵ, λ_f_2(δ_f) = λ_2(δ), and if  λ_1(δ) ≠ϵ then j=i+1; else j=i.


  * In backward gadget, for each state (q,i) ∈_S, we add a transition δ_b = ((p,j), a,(q,i))  such that 


  * if i>0, then λ_b_1(δ_b) = λ_1(δ), λ_b_2(δ_b) = ϵ, and if  λ_2(δ) ≠ϵ then  j=i-1; else j=i.

  * if i<0, then λ_b_1(δ_b) = ϵ, λ_b_2(δ_b) = λ_2(δ), and if  λ_1(δ) ≠ϵ then j=i+1; else j=i.



We construct such a forward and backward gadget for each SCCs.
For each state q in an SCC with a set of states S, we construct an automaton _S_q by concatenating _S,  induced with states S, and _S with existing transitions and labels. Additionally, following transitions are added.


  * For each state (p,0) ∈_S, p ∈, add ((p,0), ϵ, p) with ϵ output labels.

  * For each state p ∈, (p,0) ∈_S, add (p, ϵ, (p,0)) with ϵ output labels.

Let λ_1' = λ_f_1∪λ_1 ∪λ_b_1 and λ_2' = λ_f_2∪λ_2 ∪λ_b_2 be the output labels in _S_q, and ο_1', ο_2' maps each state to ϵ in _S_q. Let the initial state of _S_q being (q,∂_q) and final state being (q,-∂_q). It is easy to see that the automaton _S_q is unambiguous and is of polynomial size w.r.t. . To verify <Ref>, it suffices to check if the functional transducers  ⟨_S_q, λ_1',ο_1'⟩ and  ⟨_S_q, λ_2',ο_2'⟩ are equivalent for each state q in a SCC with a set of states S. 

Next we show closeness w.r.t. transposition distance. 
We write u ≡ v to denote that words u and v are permutations of each other. The alphabetic vector of a word over the alphabet A, denoted by u⃗, is the sequence (|w|_a_i)_a_i∈ A for some fixed ordering of A. It is easy to observe that two words are permutations of each other if their alphabetic vectors are the same.

Transposition distance between _1 and _2 is unbounded if and only if one of the following holds


  *  There is a pair (u,v) ∈ M'_q_0,q_f, q_f∈ F such that u≢v.

  *  There exists a state q∈ Q and (u,v) ∈ M_q,q such that |u|=|v| > ∂_q, and u' ≠ v' where (u',v')=_∂_q(u,v).

  *  There exists a state q∈ Q such that M_q,q is infinite, and for each pair (u,v) ∈ M_q,q of length at least |∂_q|, _∂(u,v) is identical. Further, there are pairs (u,v)∈ M_q,q and (α,β) ∈ M_q_0,q (resp. M_q,q_f) such that: If ∂_q≥ 0, then α≢β·(u,v) (resp. (u,v) ·α≢β), and if ∂_q < 0, then α·(u,v) ≢β (resp. α≢(u,v) ·β).
 



(←): It is obvious that if <Ref> is true, then the transposition distance between _1 and _2 is unbounded. Therefore we assume that the output pairs of the transducers are permutations of each other. For <Ref>, the proof is the same as in <Ref>.  Next we consider <Ref>. The cases are symmetric. Assume 
that there exist a pair (u,v)∈ M_q,q, (α,β) ∈ M_q_0,q, and WLOG ∂_q≥ 0  such that 
α≢β·(u,v). Let (α',β') be some pair in M_q,q_f. Consider the pair (u_i = α u^iα', v_i = β v^iβ'), i≥ 1.  

Let (x,x) = _∂_q(u,v), z_1 = (u,v), z_2 = (u,v). 
By assumption α≢β z_1, and hence  z_2α' ≢β'. 
Since interior of (u,v) is (x,x), we can deduce that α z_2α' ≡β z_1β'. Therefore 
α⃗- β⃗ ⃗z⃗_⃗1⃗ = z⃗_⃗2⃗α⃗'⃗- β⃗'⃗. This means that the transpositions have to cancel out the differences in the vectors at each end of the word. We can prove by induction that it requires at least |x| transpositions to mitigate a difference of 1, while keeping the alphabetic vector of the middle portion the same.
Hence we deduce that d_t(u_i,v_i) ≥ i.

(→): If d_t(_1,_2) ∈∞, either there is a pair of outputs (u,v) such that d_t(u,v)=∞ (This is <Ref>), or all the output pairs are permutations of each other and there is an infinite set of pairs S={ (u_i,v_i) | i>0} such that d_t(u_i,v_i) ≥ i.  

In the latter case, we show that either <Ref> or <Ref> holds. We say the set S is error-bounded if there is an r>0 such that u_i and v_i differ in at most r positions. 
Clearly, there are sets with bounded errors on which d_t is infinite. We do case analysis.  

If there is an infinite set of pairs S={ (u_i,v_i) | i>0} such that d_t(u_i,v_i) ≥ i that is not error-bounded, we proceed as in the proof of <Ref> and obtain <Ref> by pigeonhole principle.

If the set of all output pairs is error-bounded, then clearly for states q such that M_q,q is infinite, the interior of all the sufficiently large pairs in M_q,q are identical. Moreover since the output pairs are permutations of each other there is a state q such that |M_q,q| =∞ and there is a partial run from q_0 to q (or a partial run from q to q_f) whose output words are not permutations of each other.  




    Deciding <Ref>:

The <Ref> in <Ref> is same as that of characterisation in  <Ref>, and thus can be checked in polynomial time. For checking <Ref>, it suffices to check if all the paths between any two strongly connected components in  have the same alphabetic vectors. Towards this, first topologically sort the strongly connected components in .  Consider any two adjacent SCCs with a set of states S_1 and S_2, respectively in the topological sort of  with directed paths from states in S_1 to that of S_2. Our aim is to check if all the paths from a state in S_1 to a state in S_2 have the same alphabetic vector. For this, we construct a induced subgraph of , say _I, with S_1 ∪ S_2 being the set of states, along with all edges associated with it. Let S_1' be the states in S_1 that has an outgoing edge to next SCC in _I and S_2' be the set of states in S_2 that has an incoming edge from previous SCC in _I. Assume that the induced graph is trimmed, i.e., any state is reachable from a state in S_1' and co-reachable from a state in S_2'. For each state in the induced subgraph, we maintain a vector/ sequence of length |A| for some fixed ordering of A where A is the alphabet of  such that each position in the vector tells the difference in the count of a letter encountered till now. It can either be a positive value or a negative value. For example, for A= {1,b}, (2    -3) means there are 2 a's more (or less) in the first (or second) component of the output and there are 3 b's less (or more) in the first (or second) component of the output seen till now.  Initially, for all states in S_1' in _I we associate a zero vector.  For each transition in  involving states in _I, we compute the vector of the target state from the computed vector of the initial state. For any state, if there are two different vectors associated, then since A_I is trimmed, there exist a path from S_1' to S_2' with different alphabetic vector. Thus, for each state in _I, there is a unique vector. Finally, we need to check if the vector associated with each state in S_2' is a zero vector. Otherwise, there exist a path from S_1' to S_2' with different alphabetic vector. Hence, <Ref> can be checked in polynomial time. It is easy to see that if both <Ref> and <Ref> are not satisfied, then <Ref> is also not satisfied. 

Therefore, <Ref> and <Ref> can be verified for _1 and _2 in polynomial time. Thus, closeness of sequential and unambiguous transducers w.r.t. hamming and transposition distance is decidable in polynomial time.



 §.§ k-closeness of Hamming and Transposition distances



We have shown that using <Ref>, k-closeness is decidable for all metrics in Table <ref>. To check if two transducers _1 and _2 are k-close, we check if they have the same domain and they are close w.r.t. the length metric (otherwise they are neither close nor k-close). If so, we check if the domain T is same as the domain of _1_2dk.  From the construction used in <Ref>, the underlying automaton of f__1,_2^≤ k can be of exponential (as it has to keep track of the unprocessed words). So, the complexity of the k-closeness algorithm is EXPSPACE. However, for hamming and transposition distance, using the characterisations used for deciding their closeness (see <Ref> and <Ref>), we give a co-NP procedure for deciding k-closeness and co-NP ∩ NP procedure for computing the distance.

k-closeness w.r.t. Hamming and Transposition distance are decidable for sequential and unambiguous transducers in co-NP time.


Given two unambiguous transducers, check in polynomial time that if they are close w.r.t. Hamming (or Transposition) distance. If not, then the distance is ∞ and they are not k-close. Assume they are close. 

By <Ref>, it suffices to consider two sequential transducers with a common underlying DFA. Let _1 = ⟨, λ_1, ο_1⟩ and _2 = ⟨, λ_2, ο_2⟩ be two sequential transducers. 


Since T_1 and T_2 are close, from Condition (2) in  <Ref> and Condition 2.(b) in  <Ref>, we get that the for any state q in , (q) produces only identical pair of outputs. In fact, we can ignore the  of the loops, and by only keeping  and  of any loops, we construct a polynomially sized acyclic automaton from  such that distance of _1 and _2 equals to the maximum over the minimum edits required in any accepting path of the acyclic automaton. Towards this, we construct a forward and backward gadget similar to the one constructed for deciding <Ref>. However, in this case, instead of trimming the  (resp. ) in the forward (resp. backward) gadget, we keep only  (resp. )  and make the other component ϵ. We construct such a forward and backward gadget for each SCCs in .  For an SCC, we combine the forward and backward gadgets by merging the states of the form (p,0) in both of these gadgets where p is a state in the SCC. This combined gadget is acyclic.

Given , we topologically sort the strongly connected components. We replace each SCC with its combined forward and backward gadget. For any transition (p,a,q) between two adjacent SCC, we add a transition from ((p,-∂_p), a, (q,∂_q)) connecting the combined gadgets of the two SCCs. Therefore, we get a polynomially sized acyclic automaton, say _T, from  by removing the  of any state in  and keeping the initial and final states the same as that of . Now, it suffices to check if all paths from initial to the final state in the acylic automaton require only at most k edits (substitutions in the case of Hamming distance, while adjacent transpositions in the case of Transposition distance) to convert the output of the first transducer to that of second. The complement of this problem is asking if there exists a path that requires at least k+1 edits to convert one output to another. This is in NP since given a certificate , we can polynomially compute the number of edits required to convert one output to another (for hamming - 𝒪(n) and for transposition - 𝒪(nlogn) <cit.> where n is the length of the output words), and hence verify polynomially that whether it requires k+1 edits. Since the complement of this problem is in NP, the problem is in co-NP.


As a consequence, we get the following result.


Computing distance of two transducers w.r.t. Hamming as well as transposition distance is in co-NP ∩ NP.



First, determinine the closeness in polynomial time. If not close, then distance is ∞. If close, then we can construct an polynomially sized acyclic automaton _T such that the distance equals to the maximum over the minimum edits required in any accepting path.  In fact, the distance is bounded by product of the number of transitions in _T and the maximum value in the output length on any single transition. Let b denote the bound on the distance. Now, we can compute the exact distance using k-closeness in two ways. One way, is to iterate k over {0, 1, …, b}, and check for each k that every accepting path in _T requires at most k edits (which is in co-NP). If not, increment k and continue. Else, k is the distance between T_1 and T_2.  Hence, computing distance is in co-NP. The other way is to iterate k over {b, b-1, … , 1}, and for each k, check if there exists a accepting path with at least k edits (which is in NP). If yes, then k is the required distance between T_1 and T_2. Otherwise, decrement k and continue. Hence, computing distance is also in NP.





§ DISCUSSION AND CONCLUSION


 It is shown that  distance between two rational functions w.r.t. common edit distances is computable. The related notions of diameter of a rational relation, and  the index of a rational relation in the composition closure of another are also computable. We leave open the question of finding the precise computational complexity of the problems in Tables <ref>, <ref> and <ref>. 
 


The current decision procedure for closeness w.r.t. conjugacy and Levenshtein family of distances proceeds through the analysis of rational expressions. One could directly work on automata, but it is not enough to check for the conjugacy of simple cycles, as there can be complex strongly connected components. In such cases, a decidability proof for conjugacy can be achieved by utilizing Simon's factorization forests <cit.> and checking the conjugacy of the factorization trees inductively. Sumfree expressions are doing this in essence, circumventing the need to construct the transition monoids.


Lifting these notions to infinite words, and two-way transducers is an immediate next step. Distance between one-way transducers could be seen as the diameter of a rational relation obtained by the cartesian product. However, when the transducers , are two-way or polyregular, the relation {((w),(w)) | w ∈()} need not be rational. It remains to develop techniques for checking the conjugacy of non-rational relations. 

An interesting question is: given two functional transducers _1 and _2 with bounded distance, does there exist a transducer  such that _2 is equivalent to a cascading composition of _1 and ? This is often called the repair problem and is well-studied between two regular languages <cit.>.





