# Answer Set Programming for Regular Inference
## Appendix A How Answer Sets Are Computed  
Let \(\Pi\) be a grounded program, and let \(\mathcal{A}\) be a set of atoms occurring in \(\Pi\). Assume that atom \(z\) is not in \(\mathcal{A}\). Observe that every grounded program \(\Pi\) that has rules  
\[\gets b_{1},\ldots,b_{k},\sim c_{1},\ldots,\sim c_{m}. \tag{1}\]  
with empty head, can be transformed to a program without such rules by inserting \(z\) and \(\sim\)\(z\) in this manner:  
\[z\gets b_{1},\ldots,b_{k},\sim c_{1},\ldots,\sim c_{m},\sim z. \tag{2}\]  
A grounded program without empty-headed rules will be called _normal_.  
A rule \(r\) of the form:  
\[a\gets b_{1},\ldots,b_{k}. \tag{3}\]  
where there is no default negation in the body, and the head is not empty, will be called _positive_. A program that contains only positive rules will be called positive too. We will denote by \(\text{head}(r)\) the  
\begin{table}
\begin{tabular}{l c c c c} \hline \hline
**Problem** & **ASP** & **RA-PS1** & **RA-PS2** & **OA-PS1** & **OA-PS2** \\ \hline a\(6\)words28 & 4 & 3 & 3 & 3 & 3 \\ a\(6\)words33 & 7 & 3 & 3 & 3 & 3 \\ a\(6\)words34 & 5 & 3 & 3 & 3 & 3 \\ a\(6\)words36 & 4 & 3 & 3 & 3 & 3 \\ a\(8\)words40 & 3 & 3\({}^{*}\) & 3\({}^{*}\) & 3\({}^{*}\) & 3\({}^{*}\) \\ a\(8\)words41 & 5 & 3 & 3 & 3 & 3 \\ a\(8\)words42 & 4 & 4\({}^{*}\) & 4\({}^{*}\) & 4\({}^{*}\) & 4\({}^{*}\) \\ a\(8\)words43 & 4 & 3 & 3 & 3 & 3 \\ a\(8\)words45 & 5 & 4 & 4 & 4 & 4 \\ a\(8\)words46 & 3 & 3\({}^{*}\) & 3\({}^{*}\) & 3\({}^{*}\) & 3\({}^{*}\) \\ \hline \hline \end{tabular}
\end{table}
Table 4: \(Cont\).  
set \(\{a\}\), and by \(\text{body}(r)\) the set \(\{b_{1},\ldots,b_{k}\}\). Now, let us define how a positive program \(P\) can act on a set of atoms \(X\subseteq\mathcal{A}\) (here \(\mathcal{A}\) is a set of atoms occurring in \(P\)):  
\[X^{P}=\{\text{head}(r)\mid r\in P\text{ and body}(r)\subseteq X\}.\] (A4)  
This operation can be repeated and we define:  
\[X^{P^{1}}=X^{P}\quad\text{and}\quad X^{P^{i}}=(X^{P^{i-1}})^{P}.\] (A5)  
It is easy to see that \(\text{Cn}(P)=\bigcup_{i\geq 1}\mathcal{O}^{P^{i}}\). Because for a certain \(i\) the equation \(X^{P^{i}}=X^{P^{i+1}}\) holds, determining \(\text{Cn}(P)\) is straightforward and fast.  
Consider any normal program \(\Pi\). We recall from Section 2.3 that a set \(X\subseteq\mathcal{A}\) is an answer set of \(\Pi\) if \(X=\text{Cn}(\Pi^{X})\) (please do not confuse the reduct with program's acting on a set of atoms). Take two sets, \(L\) and \(U\), such that \(L\subseteq X\subseteq U\) for an answer set \(X\) of \(\Pi\). Observe that: (i) \(X\subseteq\text{Cn}(\Pi^{L})\), and (ii) \(\text{Cn}(\Pi^{U})\subseteq X\). Thus we get:  
\[L\cup\text{Cn}(\Pi^{U})\subseteq X\subseteq U\cap\text{Cn}(\Pi^{L}).\] (A6)  
The last property is a recipe for expanding the lower bound \(L\) and cutting down the upper bound \(U\). The procedure in which we replace \(L\) by \(L\cup\text{Cn}(\Pi^{U})\) and then \(U\) by \(U\cap\text{Cn}(\Pi^{L})\) as long as \(L\) or \(U\) are changed, will be called _narrowing_. At some point we get \(L=U=X\). When we start from \(L=\emptyset\), \(U=\mathcal{A}\), then there are also two more possibilities: \(L\
ot\subseteq U\) (there is no answer set), and \(L\subset U\). In the latter case we can take any \(a\in U-L\) and check out two paths: \(a\) should be included into \(L\) or \(a\) should be excluded from \(U\). This leads to Algorithm A1 [19]:  
```
Solve\((\Pi,L,U)\) \((L,U)\leftarrow\text{narrowing}(\Pi,L,U)\) if\(L\
ot\subseteq U\)then return if\(L=U\)then output \(L\) else choose \(a\in U-L\) Solve\((\Pi,L\cup\{a\},U)\) Solve\((\Pi,L,U-\{a\})\)
```  
**Algorithm A1**Final algorithm  
Which outputs all answer sets of a program \(\Pi\) provided that it had been invoked with \(\text{Solve}(\Pi,\emptyset,\mathcal{A})\). The pessimistic time complexity of this algorithm can be assessed by the recurrence relation \(T(n)=2T(n-1)+n^{2}\), where \(n=|U|-|L|\), which gives us the exponential complexity \(T(n)=O(2^{n})\).