# 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
### The Second \(O(n^{2}d)\) Algorithm for Edit Distance  
Algorithm PrelimDistInpAlter  
1. Input: NFA \(\mathbf{a}\)
2. Let \(B_{\mathbf{a}}\) be the bound in Lemma 2
3. Let \(\min\gets 1\) and \(\max\gets B_{\mathbf{a}}-1\)
4. Perform binary search to find the largest \(k\) in \(\{\min,\ldots,\max\}\) for which \(L(\mathbf{a})\) is error-detecting for \(\operatorname{sid}(k)\) as follows: **while** (\(\min\leq\max\)) 1. Let \(k\leftarrow\lfloor(\min+\max)/2\rfloor\) 2. Construct the transducer \(\mathbf{i}\mathbf{a}_{k}\) (see Figure 2) 3. Construct the transducer \(\mathbf{t}^{\prime}_{k}\leftarrow\mathbf{i}\mathbf{a}_{k}\downarrow\mathbf{a}\uparrow\mathbf{a}\) 4. If \(\big{(}R(\mathbf{t}^{\prime}_{k})\ =\emptyset\big{)}\) let \(\min\gets k+1\) Else let \(\max\gets k-1\)
5. **return** min  
We discuss now how to improve the above algorithm. The two observations we made at the beginning of Section 4 apply here as well if, instead of partial identity of \(\mathbf{t}^{\prime}_{k}\), we talk about the emptiness of \(\mathbf{t}^{\prime}_{k}\). Thus, we want the improved algorithm to construct in turn \(\mathbf{t}^{\prime}_{1},\mathbf{t}^{\prime}_{2},\ldots\) until the first \(\mathbf{t}^{\prime}_{d}\) with \(R(\mathbf{t}^{\prime}_{d})\
eq\emptyset\). Moreover, when \(\mathbf{t}^{\prime}_{k}\) has been constructed and realizes \(\emptyset\), we continue in the next step with new transitions added to \(\mathbf{t}^{\prime}_{k}\) in order to get \(\mathbf{t}^{\prime}_{k+1}\). **Optimized construction of \(\mathbf{t}^{\prime}_{k+1}\) from the trim \(\mathbf{t}^{\prime}_{k}\)**. Suppose that the trim \(\mathbf{t}^{\prime}_{k}\) has been constructed, where initially \(\mathbf{t}^{\prime}_{1}\leftarrow\mathbf{i}\mathbf{a}_{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 two sets of new transitions: the new transitions  
\[([k],q,q^{\prime})\xrightarrow{x/y}([k+1],r,r^{\prime}), \tag{23}\]  
where \(x/y\) is an error and \(q\xrightarrow{x}r\), \(q^{\prime}\xrightarrow{y}r^{\prime}\) are transitions in \(\mathbf{a}^{\lambda}\); and the new transitions  
\[([k,a],q,q^{\prime})\xrightarrow{\sigma/\lambda}([k+1,a],r,r^{\prime}), \tag{24}\]  
where \(a,\sigma\in\Sigma\), and \(q\xrightarrow{\sigma}r\), \(q^{\prime}\xrightarrow{\lambda}r^{\prime}\) are transitions in \(\mathbf{a}^{\lambda}\). Note that the total numbers of new transitions and states created in the first phase are \(O(|T_{\mathbf{a}}|^{2}r^{2})\) and \(O(|Q_{\mathbf{a}}|^{2}r)\), respectively. After the first phase, the incremental construction proceeds from the new states \(([k+1],r,r^{\prime})\) and \(([k+1,a],r,r^{\prime})\). Any new transition must be of the form  
\[([k+1],r,r^{\prime})\xrightarrow{\sigma/\sigma}([k+1],t,t^{\prime})\quad \text{or}\quad([k+1,a],r,r^{\prime})\xrightarrow{\sigma/\sigma}([k+1],t,t^{ \prime}), \tag{25}\]  
where \(\sigma\in\Sigma\) and, in the second case above, \(\sigma\
eq a\). This is because the transducer \(\mathbf{i}\mathbf{a}_{k+1}\) has only transitions of the form \([k+1]\xrightarrow{\sigma/\sigma}[k+1]\) and \([k+1,a]\xrightarrow{\sigma/\sigma}[k+1]\), with \(\sigma\
eq a\), going out of the state \([k+1]\). The incremental 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).