# 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
### An Input-Altering Transducer for Edit-Distance  
We shall define the input-altering transducer \(\mathbf{ia}_{k}\), which is partially shown in Figure 2. The value \(i\) in a state \([i]\) or \([i,a]\) is called the _error counter_, meaning that any path from \([0]\) to a state with error counter \(i\) has to be labeled \(u/v\) such that \(\delta(u,v)\leq i\). More precisely, we will define the edges such that a state \([i,a]\) can be reached from \([0]\) via a path with label \(u/v\) if and only if \(u=vax\) for some word \(x\) and \(i=|ax|\), thus, \(v\) is a proper prefix of \(u\) and state \([i,a]\) remembers the left-most letter of \(u\) that occurs after its prefix \(v\). A state \([i]\) with \(i\geq 1\) can only be reached via a path labeled \(u/v\) from \([0]\) if \(1\leq\delta(u,v)\leq i\), thus, \(u\
eq v\). Furthermore, we make sure that for \(u\
eq v\) such that neither \(u\leq_{p}v\) nor \(v\leq_{p}u\) there is a path from \([0]\) to \([\delta(u,v)]\), which is labeled by \(u/v\) or \(v/u\). **Definition 1**. : _The transducer_  
\[\mathbf{ia}_{k}=(Q,\Sigma,E,[0],F)\]  
_is defined as follows. The set of states is_  
\[Q=\{[i]\ |\ 0\leq i\leq k\}\cup\{[i,a]\ |\ 1\leq i\leq k,a\in\Sigma\}\]  
_with all but the initial state \([0]\) being final states:_  
\[F=Q\setminus\{[0]\}.\]  
_The transitions in \(\mathbf{ia}_{k}\) can be divided into the four sets of edges \(E=E_{0}\cup E_{s}\cup E_{i}\cup E_{d}\). The transitions from \(E_{0}\) do not introduce any error, edges from the other sets model one substitution (\(E_{s}\)), insertion (\(E_{i}\)), or deletion (\(E_{d}\)):_  
\[E_{0}= \Big{\{}[i]\xrightarrow{\sigma/\sigma}[i]\ \Big{|}\ \sigma\in \Sigma,0\leq i\leq k\Big{\}}\cup, \tag{13}\] \[\Big{\{}[i,a]\xrightarrow{\sigma/\sigma}[i]\ \Big{|}\ a,\sigma\in \Sigma,a\
eq\sigma,1\leq i\leq k\Big{\}},\] (14) \[E_{s}= \Big{\{}[i]\xrightarrow{\sigma/\tau}[i+1]\ \Big{|}\ \sigma,\tau\in \Sigma,\sigma\
eq\tau,0\leq i<k\Big{\}},\] (15) \[E_{i}= \Big{\{}[i]\xrightarrow{\lambda/\sigma}[i+1]\ \Big{|}\ \sigma\in \Sigma,1\leq i<k\Big{\}},\] (16) \[E_{d}= \Big{\{}[0]\xrightarrow{a/\lambda}[1,a]\ \Big{|}\ a\in\Sigma\Big{\}}\cup,\] (17) \[\Big{\{}[i]\xrightarrow{\sigma/\lambda}[i+1]\ \Big{|}\ \sigma\in \Sigma,1\leq i<k\Big{\}}\cup,\] (18) \[\mathbf{ia}_{k}=(Q,\Sigma,E,[0],F)\]0  
**Terminology**. If \(\mathbf{t}=(Q,\Sigma,T,q_{0},F)\) is a transducer in standard form, then, we write \(\mathbf{t}^{\mathbf{e}}\) for the NFA  
\[\mathbf{ia}_{k}=(Q,\Sigma,E,[0],F)\]1  
\[\mathbf{ia}_{k}=(Q,\Sigma,E,[0],F)\]2 A segment of the input-altering transducer \(\mathbf{ia}_{k}\): for each \(a\in\Sigma\) the complete transducer has \(k\) states of the form \([i,a]\). The labels \(\sigma\) and \(\tau\) on an edge mean: one edge for each \(\sigma,\tau\in\Sigma\) with \(\sigma\
eq\tau\); for some edge sets, additional restrictions apply denoted, for example, by \(|_{\sigma\
eq a}\). over the edit alphabet \(E_{\Sigma}\), where the labels of the transitions in \(\mathbf{t}\) are viewed as elements of \(E_{\Sigma}\). Note that, the label of a path \(P\) in \(\mathbf{t}\) is a pair of words \((u,v)\), whereas the label of the corresponding path in \(\mathbf{t}^{\mathbf{e}}\), which we denote as \(P^{\mathbf{e}}\), is an edit string \(h\) such that \(\mathrm{inp}(h)=u\) and \(\mathrm{out}(h)=v\). This type of NFA is called an eNFA in [23]. Definition 2: An edit string \(h\) of nonzero weight is called _reduced_, if (a) the first error in \(h\) is not an insertion, and (b) if the first error in \(h\) is a deletion of the form \((a/\lambda)\), then the first non-deletion edit operation that follows \((a/\lambda)\) in \(h\) (if any) is of the form \(\sigma/\sigma\) with \(\sigma\in\Sigma\setminus\{a\}\). **Example. ** The edit string \((a/a)(a/b)(a/\lambda)(\lambda/a)\) is reduced as its first error is a substitution. The edit string \((a/a)(a/\lambda)(b/b)(b/a)\) is reduced as well. The edit string \((\lambda/a)(a/a)\) is not reduced as it starts with an insertion, and the edit string \((a/\lambda)(b/a)(b/b)\) is not reduced either.