# Answer Set Programming for Regular Inference
## 4 Experimental Results
### Compared Algorithms
This is so, because there is no universal ordering method assuring fast convergence to the solution. The orderings used in the analyzed algorithms are _deg_, _mmex_, and _mmex_. The _deg_ ordering is a static ordering method based on a variable degree, i.e., the number of constraints the variables are involved in. The ordering does not change as the algorithm progresses. The _mmex_ and _mmex_ orderings change dynamically while the algorithm runs. They aim at satisfying first the equations related to examples, or counter-examples, respectively. The Parallelization Scheme 1 (PS1) maximizes the number of sets \(F\) processed simultaneously. If the number of available processes is greater than the number of sets \(F\) to be analyzed, we assign multiple variable orderings (VOs) to each set. In the RA-PS1 algorithm this assignment is performed randomly, while in the OA-PS1 algorithm, the _deg_, _mmex_, and _mmex_ methods are ordered by their complexity and chosen in a round robin fashion. The Parallelization Scheme 2 (PS2) maximizes the number of variable orderings applied to the same set \(F\). This way we shorten the time needed to obtain an answer whether an NFA exists for the given set \(F\). If the number of available processes is smaller than the product of the number of sets \(F\) and the number of variable orderings used, we need to choose the sets \(F\) to be processed first. In the RA-PS2 algorithm we choose them at random, while in the OA-RS2 algorithm, we analyze first the sets for which the size of \(F\) is smaller. **Example 3**. : _Let us consider the problem given in Example 1. Since \(k=2\) and \(\epsilon\
otin(S_{+}\cup S_{-})\), the following sets \(F\) can be defined: \(F_{1}=\{q_{0}\}\), \(F_{2}=\{q_{1}\}\), and \(F_{3}=\{q_{0},q_{1}\}\). Let us also assume that we can use the three VOs discussed before. Finally, let the number of processes \(p=3\) (denoted by \(p_{i}\), for \(i=0,1,2\)). We can have the following example configurations of algorithms RA-PS1, RA-PS2, OA-PS1, OA-PS2:_  
1. _Algorithm RA-PS1--process_ \(p_{0}\) _gets_ \((F_{1},VO_{3})\)_; process_ \(p_{1}\) _gets_ \((F_{2},VO_{2})\)_; process_ \(p_{2}\) _gets_ \((F_{3},VO_{3})\)_. Each process uses a single VO to analyze one of the possible sets_ \(F_{i}\)_,_ \(i=1,2,3\)_. There is no guarantee that all VOs are used at least once._  
Figure 3: An inferred NFA. Algorithm RA-PS2--process \(p_{0}\) gets \((F_{2},VO_{1})\); process \(p_{1}\) gets \((F_{2},VO_{2})\); process \(p_{2}\) gets \((F_{2},VO_{3})\). Each process uses a different \(VO\) to analyze just one set \(F\) at a time (chosen randomly). If there is no solution for set \(F_{2}\), we need to repeat the above assignments but this time for the set \(F_{1}\) or \(F_{3}\) (again chosen randomly). We repeat the above procedure until the solution is found. 3. Algorithm OA-PS1--process \(p_{0}\) gets \((F_{1},VO_{1})\); process \(p_{1}\) gets \((F_{2},VO_{2})\); process \(p_{2}\) gets \((F_{3},VO_{3})\). Each process uses a single \(VO\) to analyze one of the possible sets \(F_{i}\), \(i=1,2,3\), but this time the VOs are assigned according to a predefined order. 4. Algorithm OA-PS2--process \(p_{0}\) gets \((F_{1},VO_{1})\); process \(p_{1}\) gets \((F_{1},VO_{2})\); process \(p_{2}\) gets \((F_{1},VO_{3})\). Each process uses a different \(VO\) to analyze just one set \(F\) at a time, but this time we start with \(F_{1}\) followed by \(F_{2}\) and \(F_{3}\) (unless the solution is found at some stage). Note that in Parallelization Scheme 2, obtaining a negative answer, i.e., that an NFA does not exist for the given set \(F_{i}\), by means of one \(VO\) allows us to stop the execution of other VOs and move on to another set \(F_{j}\), \(i\
eq j\).