# Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers
## 6 Implementation and Testing  
As both algorithms DistErrDetect and DistInpAlter have the same theoretical complexity, we chose to implement one of the two. We chose to implement DistInpAlter because it requires a simpler test for each constructed transducer (although \(\mathbf{i}\mathbf{a}_{k}\) is slightly more complex than \(\mathbf{s}\mathbf{i}\mathbf{d}_{k}\), the test for partial identity, [6], is more sophisticated than testing merely for existence of final states). We have also implemented the preliminary algorithm PrelimDistInpAlter.  
Our implementation uses the FAdo package for automata, version 1.3.5.1, [7], which is well maintained and provides several useful tools for manipulating automata. We have performed several tests (All tests were performed on a laptop with the following specification. Make: Apple, Model: MacBook Pro, Processor 2.5 GHz Intel Core i7, Memory (RAM): 16.00 GB, Operating System: macOS High Sierra Version 10.13.6.) for the correctness of these algorithms, as well as two sets of tests for the time complexity, which confirm the theoretical result that DistInpAlter is indeed faster than PrelimDistInpAlter. The two sets of tests correspond to two lists of DFAs, \((\mathbf{a}_{n})\) and \((\mathbf{b}_{n})\), shown in Figures 3 and 4. The first test set is such that the desired distance is equal to \(n\), for each DFA \(\mathbf{a}_{n}\), that is, the distance grows with \(n\) and, in fact, it is a worst-case scenario where the distance is equal to the number of states of the automaton. The second test set is such that the desired distance is fixed, equal to \(2\), for all \(n\).  
Table 1 shows the actual running times (in seconds) of the two algorithms on the DFAs \(\mathbf{a}_{28},\mathbf{a}_{41},\mathbf{a}_{56},\mathbf{a}_{76},\mathbf{a}_{100}, \mathbf{a}_{124},\mathbf{a}_{152},\mathbf{a}_{184}\). The number in parentheses next to each \(\mathbf{a}_{n}\) indicates the number of transitions in \(\mathbf{a}_{n}\). The column \(d\) shows the computed edit distance, and the column \(B_{\mathbf{a}_{n}}\) shows the computed upper bound on the edit distance (used in algorithm PrelimDistInpAlter).  
Table 2 shows the actual running times (in seconds) of the two algorithms on the DFAs \(\mathbf{b}_{6},\ldots,\mathbf{b}_{13}\). Again, the number in parentheses next to each \(\mathbf{b}_{n}\) indicates the number of transitions in \(\mathbf{b}_{n}\).  
In both test sets, the empirical outcomes confirm the asymptotic outcome that the improved algorithm based on the optimized construction is faster than the preliminary one.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**DFA** & **d** & \(B_{\mathbf{a}_{n}}\) & **PrelimDistInpAlter** & **DistInpAlter** \\ \hline \(\mathbf{a}_{28}\) (28) & 28 & 28 & 0.696s & 0.078s \\ \(\mathbf{a}_{41}\) (41) & 41 & 41 & 3.977s & 0.267s \\ \(\mathbf{a}_{56}\) (56) & 56 & 56 & 12.811s & 0.691s \\ \(\mathbf{a}_{76}\) (76) & 76 & 76 & 52.086s & 1.885s \\ \(\mathbf{a}_{100}\) (100) & 100 & 100 & 159.370s & 4.841s \\ \(\mathbf{a}_{124}\) (124) & 124 & 124 & 354.306s & 10.643s \\ \(\mathbf{a}_{152}\) (152) & 152 & 152 & 998.438s & 21.991s \\ \(\mathbf{a}_{184}\) (184) & 184 & 184 & 2294.636s & 43.484s \\ \hline \hline \end{tabular}
\end{table}
Table 1: Outcomes of performance tests on the automata \((\mathbf{a}_{n})\).  
Figure 4: The automaton \(\mathbf{b}_{n}\) accepting the Levenshtein code, which consists of all binary words \(b_{1}\cdots b_{n}\) of length \(n\) such that \((\sum_{i=1}^{n}i\cdot b_{i})\%(n+1)=0\), where \({}^{\prime\prime}\%\) is the integer division remainder operation. This code has edit distance equal to 2. On the other hand, its distance for insertion/deletion errors only is 3. The automaton (before making it trim) has \(n^{2}+n+1\) states: \([n,0]\) and \([i,s]\), with \(0\leq i\leq n-1\) and \(0\leq s\leq n\). The meaning of state \([i,s]\) is that the automaton has read \(i\) bits \(b_{1}\cdots b_{i}\) and \(s=1\cdot b_{1}+\cdots+i\cdot b_{i}\). We have that \(f(i,s)=[i+1,(s+i+1)\%(n+1)]\).