# Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers
## 5 An \(O(n^{2}d)\) Algorithm for Edit Distance via Input-Altering Transducers
### An Input-Altering Transducer for Edit-Distance
The proofs of the next two lemmata are given in the appendix. Lemma 4: Let \(x,y,u,v\) be words. The following statements hold true:  
1. \(\delta(xuy,xvy)=\delta(u,v)\). 2. If \(v<_{p}u\) then \(\delta(u,v)=|u|-|v|\). 3. If \(u\
eq v\), then there is a reduced edit string \(h\) realizing \(\delta(u,v)\). Lemma 5: Let \(k\in\mathbb{N}\) and let \(u,v\) be words. The following statements hold true with respect to the transducer \(\mathbf{i}\mathbf{a}_{k}\). 1. In \(\mathbf{i}\mathbf{a}_{k}^{\mathbf{e}}\), every path from the start state \([0]\) to any state \([i]\) or \([i,a]\) has as label a reduced edit string whose weight is equal to \(i\). 2. If \(1\leq\delta(u,v)\leq k\) and \(h\) is a reduced edit string realizing \(\delta(u,v)\), then \(h\) is accepted by \(\mathbf{i}\mathbf{a}_{k}^{\mathbf{e}}\). 3. If \(v\in\mathbf{i}\mathbf{a}_{k}(u)\), then \(1\leq\delta(u,v)\leq k\). Theorem 2: For each \(k\in\mathbb{N}\), the transducer \(\mathbf{i}\mathbf{a}_{k}\) is input-altering and of size \(O(kr^{2})\), where \(r\) is the cardinality of the alphabet, and satisfies the following condition, for any language \(L\) containing at least two words  
\[\mathbf{ia}_{k}=(Q,\Sigma,E,[0],F)\]3  
Proof: By construction, it follows that \(\mathbf{t}_{k}\) is trim and has \(O(rk)\) states and \(O(kr^{2})\) transitions. Hence, it is indeed of size \(O(kr^{2})\). The third statement of Lemma 5 implies that the transducer is input-altering. Next, we show that (20) is true for all languages \(L\) containing at least two words. First, for the 'if' part, assume \(\delta(L)>k\) and consider any words \(u,v\in L\). We need to prove \(v\
otin\mathbf{i}\mathbf{a}_{k}(u)\). If \(u=v\), then this holds as \(\mathbf{i}\mathbf{a}_{k}\) is input-altering. Else, it follows from the third statement of Lemma 5. Now, for the 'only if' part, assume  
\[\mathbf{ia}_{k}=(Q,\Sigma,E,[0],F)\]4  
but, for the sake of contradiction, suppose there are different words \(u,v\in L\) such that \(1\leq\delta(u,v)\leq k\). Let \(h\) be a reduced edit string realizing \(\delta(u,v)\). By the second statement of Lemma 5, \(h\) is accepted by \(\mathbf{i}\mathbf{a}_{k}^{\mathbf{e}}\) via some path \(P^{\mathbf{e}}\) and, therefore, either of \((u,v)\) and \((v,u)\) is the label of the path \(P\) of \(\mathbf{i}\mathbf{a}_{k}\), that is, we have \(u\in\mathbf{i}\mathbf{a}_{k}(v)\) or \(v\in\mathbf{i}\mathbf{a}_{k}(u)\), which contradicts (21). Corollary 2: For each NFA \(\mathbf{a}\) accepting at least two words and for each transducer \(\mathbf{i}\mathbf{a}_{k}\), with \(k\in\mathbb{N}\), the following condition is satisfied:  
\[\mathbf{ia}_{k}=(Q,\Sigma,E,[0],F)\]5  
Proof: The statement follows from the above theorem and the fact (based on standard logic arguments) that \(R\big{(}\mathbf{i}\mathbf{a}_{k}\downarrow\mathbf{a}\uparrow\mathbf{a}\big{)} =\emptyset\) is equivalent to \(\mathbf{i}\mathbf{a}_{k}\big{(}L(\mathbf{a})\big{)}\cap L(\mathbf{a})=\emptyset\). The reason why condition \(R\big{(}\mathbf{i}\mathbf{a}_{k}\downarrow\mathbf{a}\uparrow\mathbf{a}\big{)}=\emptyset\) is preferred to the equivalent one in Theorem 2 is explained further below in the remark that follows Theorem 3.