# Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers
## Notation, Background and Preliminary Results
### Edit Strings and Edit Distance  
The alphabet \(E_{\Sigma}\) of the _(basic) edit operations_, which depends on the alphabet \(\Sigma\) of ordinary symbols, consists of all symbols \((x/y)\) such that \(x,y\in\Sigma\cup\{\lambda\}\) and at least one of \(x\) and \(y\) is in \(\Sigma\). If \((x/y)\in E_{\Sigma}\) and \(x\) is not equal to \(y\), then \((x/y)\) is called an _error_[23]. The edit operations \((a/b)\), \((\lambda/a)\), \((a/\lambda)\), where \(a,b\in\Sigma-\{\lambda\}\) and \(a\
eq b\), are called _substitution, insertion, deletion_, respectively. We write \((\lambda/\lambda)\) for the empty word over the alphabet \(E_{\Sigma}\). We note that \(\lambda\) is used as a formal symbol in the elements of \(E_{\Sigma}\). For example, if \(a,b\in\Sigma\), then \((\lambda/a)(b/b)\
eq(b/a)(\lambda/b)\). The elements of \(E_{\Sigma}^{*}\) are called _edit strings_. The _weight_ of an edit string \(h\), denoted by \(\operatorname{weight}(h)\), is the number of errors occurring in \(h\). For example, for  
\[g=(a/a)(a/\lambda)(b/b)(b/a)(b/b), \tag{5}\]  
\(\operatorname{weight}(g)=2\). The _input_ and _output_ parts of an edit string \(h=(x_{1}/y_{1})\cdots(x_{n}/y_{n})\) are the words (over \(\Sigma\)) \(x_{1}\cdots x_{n}\) and \(y_{1}\cdots y_{n}\), respectively. We write \(\operatorname{inp}(h)\) for the input part and \(\operatorname{out}(h)\) for the output part of \(h\). For example, for the \(g\) shown above, \(\operatorname{inp}(g)=aabbb\) and \(\operatorname{out}(g)=abab\). The _inverse of an edit string \(h\)_ is the edit string resulting by inverting the order of the input and output parts in every edit operation in \(h\). For example, the inverse of \(g\) shown above is  
\[(a/a)(\lambda/a)(b/b)(a/b)(b/b).\]  
The channel \(\operatorname{sid}(k)\) can be defined more rigorously via edit strings:  
\[\operatorname{sid}(k)=\{(u,v)\ |\ \ u=\operatorname{inp}(h),\ v=\operatorname{ out}(h),\ \text{for some }h\in E_{\Sigma}^{*}\text{ with }\operatorname{weight}(h)\leq k\}.\]  
The _edit (or Levenshtein) distance_[24] between two words \(u\) and \(v\), denoted by \(\delta(u,v)\), is the smallest number of errors (substitutions, insertions and deletions) that can be used to transform \(u\) to \(v\). More formally,  
\[\delta(u,v)=\min\{\operatorname{weight}(h)\ |\ h\in E_{\Sigma}^{*},\ \operatorname{inp}(h)=u,\ \operatorname{out}(h)=v\}.\]  
We say that an edit string \(h\)_realizes the edit distance between two words \(u\)_ and \(v\), if \(\operatorname{weight}(h)=\delta(u,v)\) and, either \(\operatorname{inp}(h)=u\) and \(\operatorname{out}(h)=v\), or \(\operatorname{inp}(h)=v\) and \(\operatorname{out}(h)=u\). For example, for \(\Sigma=\{a,b\}\), we have that \(\delta(ababa,babbb)=3\) and the edit string  
\[h=(a/\lambda)(b/b)(a/a)(b/b)(a/b)(\lambda/b)\]  
realizes \(\delta(ababa,babbb)\). Note that several edit strings can realize the distance \(\delta(u,v)\). If \(L\) is a language containing at least two words, then the edit distance of \(L\) is  
\[\delta(L)=\min\{\delta(u,v)\ |\ u,v\in L\ \text{and}\ \ u\
eq v\}.\]  
Testing whether a given NFA accepts at least two words is not a concern in this paper, but we note that this can be done efficiently (in linear time via a breadth first search type algorithm) [25]. The next lemma comes from [4]. The bound \(D_{\mathbf{a}}\) is always less than or equal to the number of states in the NFA \(\mathbf{a}\). Moreover, there are NFAs for which this bound is tight--see Section 6. Lemma 1: _For every NFA \(\mathbf{a}\) accepting at least two words, we have that_  
\[\delta(L(\mathbf{a}))\leq D_{\mathbf{a}},\]  
_where \(D_{\mathbf{a}}\) is the number of states in the longest path in \(\mathbf{a}\) from the start state having no repeated state._  
However, the bound \(D_{\mathbf{a}}\) is of no use in our context, as the problem of determining the length of a longest path in a given automaton, or a graph in general, is NP-complete since an algorithm solving this problem can be used to decide the existence of a Hamiltonian path; see for example [26].