Edit Distance of Finite-Valued Transducers

Let $A$ and $B$ denote finite alphabets of letters. A word is a sequence of letters. The empty word is denoted by $\epsilon$. The length of a word is denoted by $|w|$. The set of all finite words over the alphabet $A$ is denoted by $A^{\ast }$. A binary relation $R$ between two sets $U$ and $V$ is a subset of the Cartesian product $U\times V$. The domain of $R$ is defined as $\mathrm{𝑑𝑜𝑚}(R)=\{u\mid (u,v)\in R\}$. For $u\in U$, the set of elements related to $u$ under $R$ is denoted as $R(u)=\{v\mid (u,v)\in R\}$. Note that $u\in \mathrm{𝑑𝑜𝑚}(R)$ iff $R(u)$ is nonempty. A relation $R$ is said to be $k$-valued (resp. exactly $k$-valued) for some $k\ge 1$, if for all $u\in \mathrm{𝑑𝑜𝑚}(R)$, the cardinality of the set $R(u)$ is at most $k$ (resp. exactly $k$). A function $f:U\to V$ is a relation over $U\times V$ which is exactly 1-valued. The function $f$ is partial if $\mathrm{𝑑𝑜𝑚}(f)\subseteq U$.

A finite state automaton is a fundamental model of computation that accepts a set of words using finite memory.

For $a\in A\cup \{\epsilon \}$, we write $p\stackrel{𝑎}{\to }q$ whenever $(p,a,q)\in \mathrm{\Delta }$. A run of $𝒜$ on an input word $w=a_1\mathrm{\cdots }{a}_n$, where $a_i\in A\cup \{\epsilon \}$ for all $i\in [n]$, is a sequence of transitions $q_0\stackrel{a_1}{\to }{q}_1\mathrm{\cdots }\stackrel{a_n}{\to }{q}_n$. We use $q_0\stackrel{𝑤}{\to }{q}_n$ to denote this. The run is accepting if $q_0\in I$ and $q_n\in F$. The language of $𝒜$, denoted by $L(𝒜)$, is the set of words $w$ s.t. $𝒜$ has an accepting run on $w$.

We say that a finite state automaton is complete if for every state $q\in Q$ and for every input symbol $a\in A$, there exists $q^{\prime }\in Q$ s.t. $(q,a,q^{\prime })\in \mathrm{\Delta }$. An automaton is real-time if it has no transitions of the form $p\stackrel{𝜀}{\to }q$. An automaton is said to be trim if, for any state $q$, there exists at least one accepting run visiting $q$. A finite state automaton is deterministic if $I$ is a singleton set and the set of transitions is a (partial) function from $Q\times A$ to $Q$. The problem of checking equivalence is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete for nondeterministic finite state automata (NFA) [18] and in polynomial time for deterministic [17] finite state automata (DFA).

Transducers extend finite state automata by labelling each transition and each final state by an output word (possibly empty), thereby realising word-to-word relations.

We write $p{\stackrel{a\mid v}{\to }}_{𝒯}q$, if $(p,a,q)\in \mathrm{\Delta }$ and $v=\lambda (p,a,q)$. When the transducer $𝒯$ is clear from the context, we omit the subscript and simply write $p\stackrel{a\mid v}{\to }q$. A run of $𝒯$ labelled by an input word $a_1\mathrm{\cdots }{a}_n$, where $a_i\in A\cup \{\epsilon \}$ for all $i\in [n]$, is a sequence of transitions $q_0\stackrel{a_1\mid v_1}{\to }{q}_1\mathrm{\cdots }\stackrel{a_n\mid v_n}{\to }{q}_n$. We denote such a run by $q_0\stackrel{a_1\mathrm{\cdots }{a}_n\mid v_1\mathrm{\cdots }{v}_n}{\to }{q}_n$. The output word along this run is $v_1\mathrm{\cdots }{v}_n\cdot 𝒪(q_n)$. The run is accepting if $q_0\in I$ and $q_n\in F$. A loop rooted at state $q$ of $𝒯$ is a run of $𝒯$ s.t. the run starts and ends at $q$. The relation defined/recognised by $𝒯$, denoted as $[[𝒯]]\subseteq A^{\ast }\times B^{\ast }$, is defined as

Relations defined by transducers are called rational relations. For convenience, we use $𝒯(u)$ for $[[𝒯]](u)$, and use $\mathrm{𝑑𝑜𝑚}(𝒯)$ to denote $\mathrm{𝑑𝑜𝑚}([[𝒯]])$, called the domain of the transducer $𝒯$. We say that a transducer is complete (resp. real-time, trim) if its underlying automaton is complete (resp. real-time, trim). The Cartesian product of two transducers ${𝒯}_i=(Q_i,A,B,I_i,{\mathrm{\Delta }}_i,F_i,{\lambda }_i,{𝒪}_i)$ for $i\in [2]$, denoted by ${𝒯}_1\times {𝒯}_2$, is defined as the transducer $(Q_1\times Q_2,A,(B\cup \{\epsilon \})\times (B\cup \{\epsilon \}),I_1\times I_2,\mathrm{\Delta },F_1\times F_2,\lambda ,𝒪)\text{ where }$ $((p_1,p_2),a,(q_1,q_2))\in \mathrm{\Delta }$ if $(p_i,a,q_i)\in {\mathrm{\Delta }}_i$ for each $i\in [2]$, $\lambda ((p_1,p_2),a,(q_1,q_2))=({\lambda }_1(p_1,a,q_1),{\lambda }_2(p_2,a,q_2))$, and $𝒪(p_1,p_2)=({𝒪}_1(p_1),{𝒪}_2(p_2))$ for all $(p_1,p_2)\in Q_1\times Q_2$.

We will now review some important subclasses of rational relations that capture natural restrictions on transducers encountered in this work.

Let $𝒯$ be a real-time transducer. If $[[𝒯]]$ is $k$-valued for some $k\in \mathbb{N}$, then $𝒯$ is said to be finite-valued (or $k$-valued). The relations recognised by such transducers are called finite-valued rational relations. For example, the $k$-subword relation $\{(u,v)\mid u,v\in {\{a,b\}}^{\ast },v\text{ is a subword of }u\text{ of length }k\}$ is finite-valued. Since for any input word $u$, the number of possible outputs $v$ is bounded by $2^k$, corresponding to all words of length $k$ over the alphabet $\{a,b\}$.

If $[[𝒯]]$ is functional, then $𝒯$ is said to be a functional transducer. The functions recognised by functional transducers are called rational functions. An example is the function $f_{last}:u\sigma \mapsto \sigma u$ where $u\in {\{a,b\}}^{\ast },\sigma \in \{a,b\}$; that moves the last letter of the input word to the beginning. If the underlying automaton of $𝒯$ is unambiguous (i.e., has at most one accepting run on any input), then $𝒯$ is referred to as an unambiguous transducer. It is well-known that a function is recognised by a real-time transducer iff it is recognised by a rational transducer [3] iff it is recognised by an unambiguous transducer [5].

A transducer is called sequential if its underlying automaton is deterministic. Such transducers define functions known as sequential functions. In this case, the transition relation $\mathrm{\Delta }$ becomes a function $\mathrm{\Delta }:Q\times A\to Q$. Sequential functions are a strict subset of rational functions. For instance, the function $f_{last}$ is not sequential since, intuitively, the transducer recognising $f_{last}$ must guess the last letter initially.

Any finite-valued transducer is known to be (effectively) equivalent to a finite union of unambiguous transducers [21]. Consequently, any finite-valued rational relation can be expressed as a finite union of rational functions. A notable strict subclass of finite-valued rational relations is the class of multi-sequential relations, which corresponds to a finite union of sequential functions [12]. A transducer is said to be multi-sequential if it is a finite union of state-disjoint sequential transducers. The function $f_{last}$ is multi-sequential as it can be expressed as the union of two sequential functions $f_a:ua\mapsto au$ and $f_b:ub\mapsto bu$. However, the function $f_{\mathrm{𝗅𝖺𝗌𝗍}}^{\ast }$ that maps $u_1\mathrm{\#}\mathrm{\cdots }{u}_n\mathrm{\#}$, for $n\ge 1$, to $f_{\mathrm{𝗅𝖺𝗌𝗍}}(u_1)\mathrm{\#}\mathrm{\cdots }{f}_{\mathrm{𝗅𝖺𝗌𝗍}}(u_n)\mathrm{\#}$ for some separator $\mathrm{\#}$ is $1$-valued, but not multi-sequential.

A metric $d$ on a set $E$ is a mapping $d:E^2\to {ℝ}^{+}\cup \{\mathrm{\infty }\}$ satisfying the following properties. For any $u,v,w\in E$, $d(u,v)=0\iff u=v$ (separation), $d(u,v)=d(v,u)$ (symmetry), and $d(u,v)\le d(u,w)+d(w,v)$ (triangle inequality). The most commonly studied metrics between finite words are the edit distances. An edit distance between two words is the minimum number of edit operations required to rewrite one word into another if possible, and $\mathrm{\infty }$ otherwise. Different choices of permitted operations give rise to different edit distances. Table 1 lists some commonly used edit distances along with their corresponding sets of allowed operations. They are referred to as the Levenshtein family of distances, as they are equivalent up to a constant factor [2].

In the literature, the concept of distance between two words is naturally lifted to distance between a word and a set of words, or between two sets of words, and so on. The study of such extensions has received considerable attention in the literature. The distance between two languages $L$ and $L^{\prime }$ can be defined in a standard way, by resorting to the Hausdorff distance, denoted by $H_d(L,L^{\prime })$. Informally, it is defined to be the least upper bound of all the distances from an element in one set to the “closest element” in the other set. In order to precisely define the Hausdorff distance, we first introduce the notion of directed distance. The directed distance $\stackrel{\rightsquigarrow }{d}$ from $L$ to $L^{\prime }$ is defined as $\stackrel{\rightsquigarrow }{d}(L,L^{\prime })={sup}_{w\in L}{inf}_{w^{\prime }\in L^{\prime }}d(w,w^{\prime })$. The Hausdorff distance between $L$ and $L^{\prime }$ is defined as $H_d(L,L^{\prime })=\max \{\stackrel{\rightsquigarrow }{d}(L,L^{\prime }),\stackrel{\rightsquigarrow }{d}(L^{\prime },L)\}$. Distances between words and languages can be lifted to that between relations over words.

It was shown in [6, 19] that $d$ defines a metric over relations. Consequently, $R$ and $S$ are equivalent iff $d(R,S)=0$. Observe that iff $\mathrm{𝑑𝑜𝑚}(R)=\mathrm{𝑑𝑜𝑚}(S)$ and there exists a constant $k\ge 0$ s.t. for every word $u$ in the domain and for every output $v_1\in R(u)$, there exists some output $v_2\in S(u)$ with $d(v_1,v_2)\le k$, and vice-versa.

The distance between transducers $𝒯$ and $𝒮$, denoted by $d(𝒯,𝒮)$, is defined as the distance between the relations they recognise. In the case of edit distances, finite distance means that $\mathrm{𝑑𝑜𝑚}(𝒯)=\mathrm{𝑑𝑜𝑚}(𝒮)$ and for all input $u\in \mathrm{𝑑𝑜𝑚}(𝒯)$, any output of $𝒯$ on $u$ can be converted to an output of $𝒮$ on $u$ by doing a bounded number of edits, and conversely, any output of $𝒮$ on $u$ can be transformed into some output of $𝒯$ on $u$ with a bounded number of edits. This is relevant for comparing transducers with text-based output, such as spell checkers.

In general, the distance between two transducers is uncomputable. This follows from the undecidability of the equivalence problem for transducers [8], which reduces to checking whether the distance is zero. Notably, it has been shown in [2] that the distance between two functional transducers (or rational functions) is computable with respect to various edit distances, including the Levenshtein family of distances (See Table 1). An analysis of their proof gives a doubly exponential space upper bound for the Levenshtein family of distances. The computability of distance in this context relies on the notion of conjugacy of words [1].

For example, the words $aabb$ and $bbaa$ are conjugate with $x=aa$ and $y=bb$, whereas $aabb$ and $abab$ are not conjugate. The conjugacy defines an equivalence relation over words.

The proof for ($\Rightarrow$) is an adaptation of the proof of Proposition 2 from [6]. Since $d(x{u}^{k}y,x^{\prime }{v}^k{y}^{\prime })\le C$, we get $|u|=|v|$. Otherwise, as $k\in 𝕀$ increases, the length difference of $x{u}^{k}y$ and $x^{\prime }{v}^k{y}^{\prime }$ increases, and hence their distance will not be bounded. Since $|u|=|v|$, either both $u$ and $v$ are nonempty, or $u=v=ϵ$. In the latter case, $u$ and $v$ are conjugate. Assume that $u$ and $v$ are nonempty words. Take $k\in 𝕀$ s.t. $k\ge 2^C$. Since $d(x{u}^{k}y,x^{\prime }{v}^k{y}^{\prime })\le C$, there exist large portions of $u$’s and $v$’s that match. In fact, $u$’s and $v$’s overlap at least of length $|u|+|v|$. By Fine and Wilf’s¹¹1The Fine and Wilf’s theorem states that if some powers of two words $u$ and $v$ share a common factor of length $|u|+|v|-\gcd (u,v)$ then their primitive roots are conjugate. theorem, the primitive roots²²2The primitive root of a word $w$, denoted by ${\rho }_w$, is the shortest word s.t. $w={({\rho }_w)}^n$ for some $n\in \mathbb{N}$. of $u$ and $v$ are conjugate. Since $|u|=|v|$, it follows that $u$ and $v$ themselves are conjugate.

For the other direction ($\Leftarrow$), assume $u$ and $v$ are conjugate, i.e., there exist words $p,q$ s.t. $u=pq$ and $v=qp$. Hence, for every $k\ge 1$, $d(x{u}^{k}y,x^{\prime }{v}^k{y}^{\prime })=d(x{(pq)}^{k}y,x^{\prime }{(qp)}^k{y}^{\prime })\le d(xpy,x^{\prime }p{y}^{\prime })$. This is finite for $d\in \{d_l,d_{lcs},d_{dl}\}$. $◀$

Clearly, if the relative distance $\overrightarrow{d}(f,R)$ with respect to $d$ is computable, then we can decide whether and whether $\overrightarrow{d}(f,R)\le k$ for some $k\ge 0$. For the converse, assume decidability of the two boundedness problems. Given a function $f$ and a relation $R$, we first check whether . If it is not, then $\overrightarrow{d}(f,R)=\mathrm{\infty }$. Otherwise, we perform an exponential search: check whether $\overrightarrow{d}(f,R)\le k$ for $k=2^0,2^1,2^2,\mathrm{\dots }$ until the condition fails. Once an interval containing the relative distance is found, we perform a binary search on the interval $[2^n,2^{n+1}]$, $n\in \mathbb{N}$ to determine the exact value of $\overrightarrow{d}(f,R)$. $◀$

We show in the upcoming subsections that both finiteness and $k$-finiteness of relative distance of a sequential function to a multi-sequential relation w.r.t. Levenshtein family of distances are decidable (See Lemma 16 and 17). Hence, using Proposition 12, we get