# 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  
In this section, we observe that the algorithm of the previous section repeats a lot of computations, and we eliminate those repeated computations to arrive at an improved algorithm that computes the edit distance \(d\) of a trim NFA \(\mathbf{a}\) in time \(O(n^{2}dr^{2})\), where \(r\) is the cardinality of the alphabet used in \(T_{\mathbf{a}}\), and \(n=|T_{\mathbf{a}}|\). The improved algorithm is based on the following two observations:  
* The previous algorithm starts the binary search loop by constructing the transducer \(\mathbf{t}^{\prime}_{\lfloor B_{\mathbf{a}}/2\rfloor}\), but the edit distance might be much smaller than \(\lfloor B_{\mathbf{a}}/2\rfloor\). It turns out that it is more efficient in the end to construct in turn \(\mathbf{t}^{\prime}_{1},\mathbf{t}^{\prime}_{2},\ldots\) until the first \(\mathbf{t}^{\prime}_{d}\) that does not realize a partial identity. * If \(\mathbf{t}^{\prime}_{k}\) is constructed and tested that does not realize a partial identity, then the transducer \(\mathbf{t}^{\prime}_{k+1}\) is constructed from scratch and the partial identity test is repeated for the part of \(\mathbf{t}^{\prime}_{k+1}\) that corresponds to \(\mathbf{t}^{\prime}_{k}\). We shall define the transducer \(\mathbf{t}^{\prime\prime}_{k+1}\) to be the part that is added to \(\mathbf{t}^{\prime}_{k}\) in order to obtain \(\mathbf{t}^{\prime}_{k+1}\), plus some initial state. Moreover, we shall show that, if \(\mathbf{t}^{\prime}_{k}\) realizes a partial identity, then \(\mathbf{t}^{\prime}_{k+1}\) realizes a partial identity if and only if \(\mathbf{t}^{\prime\prime}_{k+1}\) does so. Thus, the partial identity test in each step will apply only to the new part that is added to the transducer of the previous step. We proceed with details based on the above observations. **Product construction of trim \(\mathbf{t}^{\prime}=\mathbf{t}\downarrow\mathbf{a}\uparrow\mathbf{a}\),** given transducer \(\mathbf{t}\) and NFA \(\mathbf{a}\). As usual in cross product constructions, the states of \(\mathbf{t}^{\prime}\) are triples of the form \((\varphi,q,q^{\prime})\), where \(\varphi\) is a state of \(\mathbf{t}\), and \(q\), \(q^{\prime}\) are states of \(\mathbf{a}\). The initial state of \(\mathbf{t}^{\prime}\) is \((\varphi_{0},q_{0},q_{0})\), where \(\varphi_{0}\) is the initial state of \(\mathbf{t}\) and \(q_{0}\) is the initial state of \(\mathbf{a}\). The construction is _incremental_, starting with the creation of \((\varphi_{0},q_{0},q_{0})\); then:  
* If state \((\varphi,q,q^{\prime})\) has been created, and there are transitions \(\varphi\xrightarrow{x/y}\psi\), \(q\xrightarrow{x}r\), \(q^{\prime}\xrightarrow{y}r^{\prime}\) of \(\mathbf{t}\), \(\mathbf{a}^{\lambda}\) and \(\mathbf{a}^{\lambda}\), respectively, then the transition \[(\varphi,q,q^{\prime})\xrightarrow{x/y}(\psi,r,r^{\prime})\] is added in \(\mathbf{t}^{\prime}\). Here, \(\mathbf{a}^{\lambda}\) is the \(\lambda\)-NFA that results if we add in \(\mathbf{a}\) the loop transitions \((q,\lambda,q)\) to all states \(q\) of \(\mathbf{a}\). The final states of \(\mathbf{t}^{\prime}\) are those constructed triples consisting of final states in \(\mathbf{t}\) and \(\mathbf{a}\). In the end, we also make \(\mathbf{t}^{\prime}\) trim. **Optimized construction of \(\mathbf{t}^{\prime\prime}_{k+1}\) and \(\mathbf{t}^{\prime}_{k+1}\) from the trim \(\mathbf{t}^{\prime}_{k}\). ** Suppose that \(\mathbf{t}^{\prime}_{k}\) has been constructed, where initially \(\mathbf{t}^{\prime}_{1}=\mathbf{sid}_{1}\downarrow\mathbf{a}\uparrow\mathbf{a}\). Constructing \(\mathbf{t}^{\prime}_{k+1}\) using \(\mathbf{t}^{\prime}_{k}\) will be done again incrementally. The _first phase_ of the incremental construction is to add the new transitions  
\[([k],q,q^{\prime})\xrightarrow{x/y}([k+1],r,r^{\prime}), \tag{8}\]  
where \(x/y\) is an error and \(q\xrightarrow{x}r\), \(q^{\prime}\xrightarrow{y}r^{\prime}\) are transitions in \(\mathbf{a}^{\lambda}\).