# Answer Set Programming for Regular Inference
## 4 Experimental Results
### Performance Comparison  
In all experiments, we used Intel (Santa Clara, California, U.S.) Xeon CPU E5-2650 v2, 2.6 GHz (8 cores, 16 threads), under Ubuntu 18.04 operating system with 190 GB RAM. The time limit (TL) was set to 1000 s. The results are listed in Table 2. In order to determine whether the observed mean difference between ASP and the remaining methods is a real CPU time decrease, we used a paired samples \(t\) test [23] pp. 1560-1565, for ASP vs. SAT, ASP vs. RA-PS1, ASP vs. RA-PS2, ASP vs. OA-PS1, and ASP vs. OA-PS2. As we can see from Table 3, \(p\) value is low in all cases, so we can conclude that our results did not occur by chance and that using our ASP encoding is likely to improve CPU time performance for prepared benchmarks. Let us explain how the mean values were computed. All TL cells were substituted by 1000. Notice that this procedure does not violate the significance of the statistical tests, because our program completed computations within the time limit for all problems (files). Thus, determining all running times would even strengthen our hypothesis. To make the advantage of the ASP-based approach over the exact parallel algorithms even more convincing let us analyze the largest sizes of automata analyzed by the algorithms within the time limit TL = 1000 s. The summary of obtained sizes is given in Table 4. Note that the table includes only the problems for which TL entries exist in Table 2. The entries marked with * denote executions in which the algorithms started running for the given \(k\) but were terminated due to the time limit, without producing the final NFA. \begin{table}
\begin{tabular}{l c c c c c c c} \hline \hline \multirow{2}{*}{**Problem**} & \multicolumn{6}{c}{**Execution**} \\ \cline{2-9}  & \multicolumn{2}{c}{**Sequential**} & \multicolumn{6}{c}{**Parallel**} \\ \cline{2-9}  & **SAT** & **ASP** & **RA-PS1** & **RA-PS2** & **OA-PS1** & **OA-PS2** & **ASP** \\ \hline a2 words27 & 148.11 & 77.46 & TL & TL & TL & TL & 10.69 \\ a2 words28 & 1.86 & 0.18 & 1.07 & 1.15 & 1.28 & 1.19 & 0.25 \\ a2 words29 & 6.40 & 0.49 & TL & TL & TL & TL & 0.40 \\ a2 words30 & 2.78 & 0.39 & 9.14 & 8.52 & 9.55 & 9.08 & 0.25 \\ a2 words31 & 2.08 & 0.52 & TL & TL & TL & TL & 0.37 \\ a2 words32 & 791.19 & 4.50 & TL & TL & TL & TL & 3.50 \\ a2 words33 & 49.72 & 1.99 & TL & TL & TL & TL & 0.93 \\ a2 words34 & 10.05 & 0.57 & 20.59 & 20.92 & 19.88 & 19.02 & 0.59 \\ a2 words35 & 0.47 & 0.09 & 0.53 & 0.38 & 0.38 & 0.38 & 0.10 \\ a2 words36 & 526.07 & 2.57 & TL & TL & TL & TL & 3.47 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Execution times of exact solving NFA identification in seconds. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Problem** & **ASP** & **RA-PS1** & **RA-PS2** & **OA-PS1** & **OA-PS2** \\ \hline a2 words27 & 8 & 6 & 6 & 6 & 6 \\ a2 words29 & 5 & 5\({}^{*}\) & 5\({}^{*}\) & 5\({}^{*}\) & 5\({}^{*}\) \\ a2 words31 & 6 & 5 & 5 & 5 & 5 \\ a2 words32 & 5 & 4 & 4 & 4 & 4 \\ a2 words33 & 7 & 5 & 5 & 5 & 5 \\ a2 words36 & 5 & 4 & 4 & 4 & 4 \\ a2 words36 & 5 & 4 & 4 & 4 & 4 \\ a2 words27 & 4 & 4 \({}^{*}\) & 4 \({}^{*}\) & 4\({}^{*}\) & 4\({}^{*}\) \\ a4 words29 & 5 & 4 & 4 & 4 & 4 \\ a4 words31 & 4 & 4 \({}^{*}\) & 4 \({}^{*}\) & 4\({}^{*}\) & 4\({}^{*}\) \\ a4 words34 & 4 & 3 & 3 & 3 & 3 \\ a4 words35 & 4 & 4 \({}^{*}\) & 4 \({}^{*}\) & 4 \({}^{*}\) & 4\({}^{*}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Sizes of NFAs reached by the parallel algorithms. The sign \({}^{*}\) means that the time limit was exceeded.