# Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers
## 3 Edit Distance via Error-Detection  
In [5], the authors discuss a conceptual method for computing integral distances of regular languages--integral means that all distance values are nonnegative integers--via the property of error-detection. In this section, we review that method and produce a _concrete_ preliminary algorithm for computing the edit distance of a regular language. A language \(L\) is _error-detecting for_ a channel \(\gamma\), [27], if no \(L\)-word can be received as a different \(L\)-word via \(\gamma\); that is (The definition of error-detection in [27] uses \(L\cup\{\lambda\}\) instead of \(L\) in Formula 6. This slight change makes the presentation here simpler and has no bearing on any existing results regarding error-detecting languages. ), for any words \(u\) and \(v\),  
\[u,v\in L\,\text{and}\,(u,v)\in\gamma\ \rightarrow\ u=v. \tag{6}\]  
Remark 1: _The error-detection method of [5] for computing inner distances of regular languages is based on the following observations, where \(\mathbf{a}\) is an NFA and \(\mathbf{t}\) is an input-preserving transducer._  
1. _A language_ \(L\) _is error-detecting for_ \(\operatorname{sid}(m)\)_, if and only if_ \(\delta(L)>m\)_._
2. \(\delta(L)\) _is equal to the positive integer_ \(k\) _such that_ \(L\) _is error-detecting for_ \(\operatorname{sid}(k-1)\) _and_ \(L\) _is not error-detecting for_ \(\operatorname{sid}(k)\)_._
3. _We have the following facts from_ [27]_. A language_ \(L\) _is error-detecting for a channel_ \(\gamma\) _if and only if the following relation is a function_ \[\gamma\cap(L\times\Sigma^{*})\cap(\Sigma^{*}\times L).\] (7) _Moreover, if_ \(\mathbf{a}\) _accepts_ \(L\) _and_ \(\mathbf{t}\) _realizes_ \(\gamma\)_, then a transducer_ \((\mathbf{t}\downarrow\mathbf{a})\) _realizing_ \(\gamma\cap(L\times\Sigma^{*})\) _can be constructed in time_ \(O(|\mathbf{t}||\mathbf{a}|)\) _and, analogously, a transducer_ \((\mathbf{t}\uparrow\mathbf{a})\) _realizing_ \(\gamma\cap(\Sigma^{*}\times L)\) _can be constructed in time_ \(O(|\mathbf{t}||\mathbf{a}|)\)_. Both constructions are cross-product constructions. In each case, the resulting transducer has_ \(O(|Q_{\mathbf{a}}||Q_{\mathbf{t}}|)\) _states and_ \(O(|T_{\mathbf{a}}||T_{\mathbf{t}}|)\) _transitions. Thus, the transducer_ \[(\mathbf{t}\downarrow\mathbf{a}\uparrow\mathbf{a})\] _realizes relation (_7_) and can be constructed in time_ \(O(|\mathbf{t}||\mathbf{a}|^{2})\)_There is an_ \(O(|T_{\mathbf{s}}|^{2}+r|Q_{\mathbf{s}}|^{2})\) _time algorithm that decides whether a given transducer_ \(\mathbf{s}\) _is functional_ _[_6; 28_]__, where_ \(r\) _is the size of the alphabet._  
Using the above observations, we present first a preliminary error-detection-based algorithm for computing the desired edit distance. Algorithm PrelimDistErrDetect  
Input: NFA \(\mathbf{a}\)  
Let \(B_{\mathbf{a}}\) be the edit distance bound in Lemma 2  
Let \(\min\gets 1\) and \(\max\gets B_{\mathbf{a}}-1\)  
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\))  
Let \(k\leftarrow\lfloor(\min+\max)/2\rfloor\)  
Construct transducer \(\mathbf{sid}_{k}\) realizing the channel \(\operatorname{sid}(k)\)--see Figure 1  
Construct the transducer \(\mathbf{t}^{\prime}_{k}\leftarrow(\operatorname{sid}_{k}\downarrow\mathbf{a} \uparrow\mathbf{a})\)  
If \(L(\mathbf{a})\) is error-detecting for \(\operatorname{sid}(k)\), let \(\min\gets k+1\)  
Else let \(\max\gets k-1\)  
**return**\(\min\)  
**Remark 2**. : _Step (3d) of the above algorithm can be computed using the transducer functionality algorithm on \(\mathbf{t}^{\prime}_{k}\), which leads again to a polynomial but expensive algorithm.