# Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers
## Notation, Background and Preliminary Results
### NFAs and Transducers  
A Nondeterministic Finite Automaton with empty transitions, \(\lambda\)_-NFA_ for short, or just _automaton_, is a quintuple \(\mathbf{a}=(Q,\Sigma,T,s,F)\) such that \(Q\) is the finite set of states, \(\Sigma\) is the alphabet, \(s\in Q\) is the start (or initial) state, \(F\subseteq Q\) is the set of final states, and \(T\subseteq Q\times(\Sigma\cup\{\lambda\})\times Q\) is the finite set of transitions or edges. Let \((p,x,q)\) be a transition of \(\mathbf{a}\). Then, \(x\) is called the _label_ of the transition, and we say that the transition _goes out_ of \(p\). We also use the notation  
\[p\xrightarrow{x}q\]  
for a transition \((p,x,q)\). The \(\lambda\)-NFA \(\mathbf{a}\) is called an _NFA_, if no transition label is empty, that is, \(T\subseteq Q\times\Sigma\times Q\). A _Deterministic_ Finite Automaton, _DFA_ for short, is a special type of NFA in which, for each state \(p\), there are no two transitions with equal labels going out of \(p\). A _path_ of \(\mathbf{a}\) is a finite sequence of consecutive transitions:  
\[(p_{0},x_{1},p_{1})(p_{1},x_{2},p_{2})\cdots(p_{\ell-1},x_{\ell},p_{\ell}), \tag{4}\]  
for some nonnegative integer \(\ell\), where we use concatenation of these transitions to denote the path. Then, if \(P_{1}\) and \(P_{2}\) are two paths such that the last state of \(P_{1}\) is equal to the first state of \(P_{2}\),  
\(P_{1}P_{2}\) denotes the path resulting by concatenating the transitions of \(P_{1}\) and \(P_{2}\). The word \(x_{1}\cdots x_{\ell}\) is called the _label_ of the path in Label (4). We write \(p_{0}\xrightarrow{x}p_{\ell}\) to indicate that there is a path with label \(x\) from \(p_{0}\) to \(p_{\ell}\). A path as above is called a _computation_ of \(\mathbf{a}\) if \(p_{0}\) is the start state. It is called an _accepting_ path/computation if \(p_{0}\) is the start state and \(p_{\ell}\) is a final state. The _language accepted_ by \(\mathbf{a}\), denoted as \(L(\mathbf{a})\), is the set of labels of all the accepting paths of \(\mathbf{a}\). The automaton \(\mathbf{a}\) is called _trim_, if every state appears in some accepting path of \(\mathbf{a}\). A (finite nondeterministic) _transducer_[17; 20] is a quintuple (In the literature, a transducer also has an output alphabet \(\Gamma\), but we consider here that \(\Gamma\) is the same as the input alphabet \(\Sigma\). Without further mention all transducers considered here are nondeterministic.) \(\mathbf{t}=(Q,\Sigma,T,s,F)\) such that \(Q,s,F\) are exactly the same as those in \(\lambda\)-NFAs, \(\Sigma\) is the alphabet, and \(T\subseteq Q\times(\Sigma\cup\{\lambda\})\times(\Sigma\cup\{\lambda\})\times Q\) is the finite set of transitions or edges. We write \((p,x/y,q)\), or \(p\xrightarrow{x/y}q\) for a transition--the _label_ here is \((x/y)\), with \(x\) being the _input_ and \(y\) being the _output_ label of the transition. The concepts of path, computation, accepting path, and trim transducer are similar to those in \(\lambda\)-NFAs. However, the label of a transducer path \((p_{0},x_{1}/y_{1},p_{1})\cdots(p_{\ell-1},x_{\ell}/y_{\ell},p_{\ell})\) is the pair \((x_{1}\cdots x_{\ell},y_{1}\cdots y_{\ell})\) of the two words consisting of the concatenations of the input and output labels in the path, respectively. The _relation realized_ by the transducer \(\mathbf{t}\), denoted by \(R(\mathbf{t})\), is the set of labels in all the accepting paths of \(\mathbf{t}\). We write \(\mathbf{t}(u)\) for the _set of possible outputs_ of \(\mathbf{t}\) on input \(u\), that is,  
\[v\in\mathbf{t}(u)\text{ if and only if }(u,v)\in R(\mathbf{t}).\]  
The transducer \(\mathbf{t}\) is called _functional_, if the relation \(R(\mathbf{t})\) is a function, that is, \(\mathbf{t}(u)\) consists of at most one word, for all input words \(u\). We say that \(\mathbf{t}\)_realizes a partial identity_, if \(v\in\mathbf{t}(u)\) implies that \(v=u\).