# Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers
## 4 An \(O(n^{2}d)\) Algorithm for Edit Distance via Error-Detection
There will be no new transitions of the form \(([i],q,q^{\prime})\xrightarrow{x/y}([k+1],r,r^{\prime})\) for \(i<k\), because the transducer \(\mathbf{sid}_{k+1}\) has no transitions from any state \([i]\) with \(i<k\) to state \([k+1]\). Note that the numbers of new transitions and new states created as in (8) are \(O(|T_{\mathbf{a}}|^{2}r^{2})\) and \(O(|Q_{\mathbf{a}}|^{2})\), respectively. After the first phase, the incremental construction proceeds from the new states \(([k+1],r,r^{\prime})\) in (8). Any new transition must be of the form  
\[([k+1],q,q^{\prime})\xrightarrow{\sigma/\sigma}([k+1],r,r^{\prime}), \tag{9}\]  
where \(\sigma\in\Sigma\). This is because the transducer \(\mathbf{sid}_{k+1}\) has only transitions of the form \([k+1]\xrightarrow{\sigma/\sigma}[k+1]\) going out of the state \([k+1]\). The process ends when no new states are created. The transitions and final states of the transducer \(\mathbf{t}^{\prime}_{k+1}\) are those in \(\mathbf{t}^{\prime}_{k}\) plus the newly created ones, after removing any new states that cannot reach a final state (thus, also \(\mathbf{t}^{\prime}_{k+1}\) is trim). The transducer \(\mathbf{t}^{\prime\prime}_{k+1}\) has as transitions and final states only the newly created ones, and has as initial state a new state \([-1]\) with transitions \([-1]\xrightarrow{\lambda/\lambda}([k],q,q^{\prime})\), for all states of the form \(([k],q,q^{\prime})\). **Lemma 3**. : _Suppose the trim transducer \(\mathbf{t}^{\prime}_{k}\) realizes a partial identity._  
* _If_ \(C_{1}\) _is a computation of_ \(\mathbf{t}^{\prime}_{k}\) _ending at a state of the form_ \(([k],p,p^{\prime})\)_, then the label of_ \(C_{1}\) _is of the form_ \((w_{1},w_{1})\)_._
* \(\mathbf{t}^{\prime}_{k+1}\) _realizes a partial identity if and only if_ \(\mathbf{t}^{\prime\prime}_{k+1}\) _does so._  
Proof. : For the first statement, consider any computation \(C_{1}\) of \(\mathbf{t}^{\prime}_{k}\) having some label \((w_{1},w^{\prime}_{1})\) and ending at a state of the form \(([k],p,p^{\prime})\). We show that \(w_{1}=w^{\prime}_{1}\). If the state \(([k],p,p^{\prime})\) is final, then \(C_{1}\) is an accepting computation, which implies \(w_{1}=w^{\prime}_{1}\), as \(\mathbf{t}^{\prime}_{k}\) realizes a partial identity. If \(([k],p,p^{\prime})\) is not a final state, then, as \(\mathbf{t}^{\prime}_{k}\) is trim, there is a path \(C^{\prime}_{1}\) from \(([k],p,p^{\prime})\) to a final state of \(\mathbf{t}^{\prime}_{k}\), where all states of that path are of the form \(([k],r,r^{\prime})\) and all labels of that path are of the form \(\sigma/\sigma\)--this is because any transition of \(\mathbf{sid}_{k}\) from state \([k]\) can only go to state \([k]\) and can only have a label of the form \(\sigma/\sigma\). Thus, there is an accepting path of \(\mathbf{t}^{\prime}_{k}\) of the form \(C_{1}C^{\prime}_{1}\) with label \((w_{1}z,w^{\prime}_{1}z)\) for some nonempty word \(z\). Then, as \(\mathbf{t}^{\prime}_{k}\) realizes a partial identity, we have that \(w_{1}z=w^{\prime}_{1}z\), which implies \(w_{1}=w^{\prime}_{1}\), as required. For the 'only if' part of the second statement, assume that \(\mathbf{t}^{\prime}_{k+1}\) realizes a partial identity. Consider any accepting computation \(C_{2}\) of \(\mathbf{t}^{\prime\prime}_{k+1}\) with some label \((w_{2},w^{\prime}_{2})\). We show that \(w_{2}=w^{\prime}_{2}\). Let \([-1]\xrightarrow{\lambda/\lambda}([k],p,p^{\prime})\) be the first transition of \(C_{2}\). Let \(C^{\prime}_{2}\) be the path that results when we remove the first transition of \(C_{2}\). By the construction of \(\mathbf{t}^{\prime}_{k+1}\), there is a computation \(C_{1}\) of \(\mathbf{t}^{\prime}_{k}\) that ends at state \(([k],p,p^{\prime})\). Let \((w_{1},w_{1})\) be the label of \(C_{1}\). Then, \(C_{1}C^{\prime}_{2}\) is an accepting computation of \(\mathbf{t}^{\prime}_{k+1}\) with label \((w_{1}w_{2},w_{1}w^{\prime}_{2})\). As \(\mathbf{t}^{\prime}_{k+1}\) realizes a partial identity, \(w_{1}w_{2}=w_{1}w^{\prime}_{2}\), which implies \(w_{2}=w^{\prime}_{2}\), as required.