# Answer Set Programming for Regular Inference
## 4 Experimental Results
### Benchmarks  
As far as we know, all standard benchmarks are too hard to be solved by pure exact algorithms. Thus, we generated problem instances using our own algorithm. This algorithm builds a set of words with the following parameters: size \(|E|\) of a regular expression to be generated, alphabet size \(|\Sigma|\), the number \(|S|\) of words actually generated and their minimum, \(d_{\min}\), and maximum, \(d_{\max}\), lengths. The algorithm is arranged as follows. First, construct a random regular expression \(E\). Next, obtain corresponding minimum-state DFA \(M\). Then, as long as a sample \(S\) is not symmetrically structurally complete (refer to Chapter 6 of [3] for the formal definition of this concept) with respect to \(M\), repeat the following steps: (a) using the Xeger library ([[https://pypi.org/project/xeger/](https://pypi.org/project/xeger/)]([https://pypi.org/project/xeger/](https://pypi.org/project/xeger/))) for generating random strings from a regular expression, get two words \(u\) and \(w\); (b) truncate as few symbols from the end of \(w\) as possible in order to obtain a counter-example \(\overline{w}\); if it succeeds, add \(u\) to \(S_{+}\) and \(\overline{w}\) to \(S_{-}\). Finally, accept \(S=(S_{+},S_{-})\) as a valid sample if it is not too small, too large or highly imbalanced. In order to ensure that these conditions are fulfilled, the equations \(|S_{+}|\geq 8\), \(|S_{-}|\geq 8\), and \(|S_{+}|+|S_{-}|\leq 1000\) hold for all our samples. In generating a random word from a regex or from  
Figure 1: An inferred non-deterministic finite automaton (NFA). an automaton we encounter a problem with, respectively, star operator and self-loops. Theoretically, there are infinitely many words matched to these fragments, so we have to bound the number of repetitions. We set this parameter to four. In this manner we produced 40 sets with: \(|E|\in[27,46]\), \(|\Sigma|\in\{2,4,6,8\}\), \(|S|\in[27,958]\), \(d_{\min}=0\), and \(d_{\max}=305\). The file names with samples have the form 'a\(|\Sigma|\)words\(|E|\).txt'. To give the reader a hint on the variability of the resulting automata, we show in Table 1 the numbers of states and transitions in each of the 40 NFAs found using our approach. We show there also the size of \(M\) and the size of minimal DFA \(D\) compatible with sample data. Example solutions from each group of problems, defined by the size of the input alphabet \(|\Sigma|\) are also shown in Figure 2. \begin{table}
\begin{tabular}{l c c c c c c c c c} \hline \hline
**Problem** & \(\mathbf{k_{0}}\) & \(\mathbf{t}\) & \(|\mathbf{M}|\) & \(|\mathbf{D}|\) & **Problem** & \(\mathbf{k_{0}}\) & \(\mathbf{t}\) & \(|\mathbf{M}|\) & \(|\mathbf{D}|\) \\ \hline a2 words27 & 8 & 32 & 20 & 15 & a6 words27 & 3 & 23 & 9 & 3 \\ a2 words28 & 3 & 6 & 7 & 3 & a6 words28 & 4 & 50 & 15 & 4 \\ a2 words29 & 5 & 22 & 10 & 6 & a6 words29 & 3 & 24 & 6 & 3 \\ a2 words30 & 3 & 7 & 6 & 3 & a6 words30 & 2 & 14 & 8 & 2 \\ a2 words31 & 6 & 13 & 12 & 7 & a6 words31 & 2 & 19 & 11 & 2 \\ a2 words32 & 5 & 10 & 10 & 5 & a6 words32 & 2 & 11 & 6 & 2 \\ a2 words33 & 7 & 19 & 17 & 8 & a6 words33 & 7 & 97 & 17 & 10 \\ a2 words34 & 4 & 13 & 6 & 5 & a6 words34 & 5 & 58 & 16 & 6 \\ a2 words35 & 3 & 6 & 6 & 3 & a6 words35 & 2 & 14 & 6 & 2 \\ a2 words36 & 5 & 23 & 9 & 8 & a6 words36 & 4 & 41 & 15 & 5 \\ a4 words27 & 4 & 32 & 10 & 4 & a8 words37 & 2 & 19 & 8 & 3 \\ a4 words28 & 3 & 16 & 14 & 3 & a8 words38 & 3 & 34 & 6 & 3 \\ a4 words29 & 5 & 34 & 6 & 6 & a8 words39 & 2 & 27 & 11 & 2 \\ a4 words30 & 3 & 15 & 7 & 4 & a8 words40 & 3 & 30 & 13 & 3 \\ a4 words31 & 4 & 23 & 12 & 4 & a8 words41 & 5 & 79 & 11 & 6 \\ a4 words32 & 3 & 18 & 6 & 3 & a8 words42 & 4 & 65 & 21 & 5 \\ a4 words33 & 4 & 24 & 12 & 4 & a8 words43 & 4 & 60 & 15 & 4 \\ a4 words34 & 4 & 21 & 16 & 4 & a8 words44 & 2 & 23 & 7 & 2 \\ a4 words35 & 4 & 28 & 23 & 4 & a8 words45 & 5 & 66 & 15 & 7 \\ a4 words36 & 2 & 9 & 5 & 3 & a8 words46 & 3 & 27 & 9 & 3 \\ \hline \hline \end{tabular}
\end{table}