Fig. 1. List processing

$$\begin{array}{l}{{m e m b e r(X,[X|Y]).}}\\ {{m e m b e r(X,[Y|Z])\leftarrow\,m e m b e r(X,Z).}}\end{array}$$
$reverse(L,R)\gets reverse(L,[\,],R)$.  $reverse([\,],R,R)$.  $reverse([X|X_s],A,R)\gets reverse(X_s,[X|A],R)$.  
$$\begin{array}{r l}{{}}&{{}{r e v e r s e(L,R)\not\subset1}}\\ {{}}&{{}{r e v e r s e([1],R,R).}}\\ {{}}&{{}{r e v e r s e([X|X_{s}],A).}}\end{array}$$
  \begin{tabular}{l l} Fig. 2. & SAT problem \\  & $s(\mathit{and}(X,Y))\gets s(X),s(Y)$. \\  & $s(\mathit{or}(X,Y))\gets s(X)$. \\  & $s(\mathit{or}(X,Y))\gets s(Y)$. \\  & $s(\mathit{or}(X,Y))\gets s(Y)$. \\ \end{tabular}  \begin{tabular}{l l}  & $s(\mathit{not}(X))\leftarrow\texttt{not}\,s(X)$. \\  & $s(A)\leftarrow\mathit{member}\,(A,[p,q,r]),\texttt{not}\,ns(A)$. \\  & $ns(A)\gets\mathit{member}(A,[p,q,r]),\texttt{not}\,s(A)$. \\ \end{tabular}  

## 8 Related Work

ASP programs with function symbols are able to encode infinite domains and recursive data structures, such as lists, trees, XML/HTML documents, time. However, some restrictions are needed to keep inference decidable and, to this end, ASP researchers have recently made several proposals (Syrj¨anen 2001; Bonatti 2004; Simkus and Eiter 2007; Gebser et al. 2007; Baselice et al. 2009; Calimeri et al. 2008; Calimeri et al. 2009). We will discuss finitelyground and FDNC programs, as they include all the other classes mentioned above.

Finitely-ground programs are DLP programs with function symbols introduced in (Calimeri et al. 2008).

If we compare this class with FP2 programs, we note that:

- Ground and nonground queries are computable for finitely-ground programs; callsafe queries are computable for FP2 programs while, in general, nonground queries are r.e.-complete.

- The answer sets of finitely-ground programs are computable because their semantics is finite. Infinite stable models are ruled out. On the contrary, FP2 programs may have infinite and infinitely many answer sets.

- Finitely-ground programs are safe, while FP2 programs admit unsafe rules.

- Odd-cycles may occur in finitely-ground programs but not in FP2 programs. The latter can be extended with odd-cyclic predicates through composition with CFSP
programs as shown in Section 7.

- Deciding whether a program is finitely-ground is semidecidable, while the class of FP2 programs is decidable.

- Finitely-ground programs are disjunctive, while FP2 is currently restricted to normal programs.
Finitely-ground and FP2 programs are not comparable due to the different recursion modes that they admit and that make finitely-ground programs suitable for a bottom-up evaluation and FP2 programs suitable for a top-down evaluation. Figures 1, 2 and 3 and Example 4.5 illustrate some programs that are FP2 but not finitely-ground.

FDNC programs (Simkus and Eiter 2007) achieve inference decidability by exploiting a tree-model property, by analogy with decidable fragments of first-order logic such as description logics and the guarded fragment. The tree-model property derives from syntactic restrictions on predicate arity and on the occurrences of function symbols (modelled around the skolemization of guarded formulae). FDNC programs can be applied to encode ontologies expressed in description logics, and are suitable to model a wide class of planning problems. Summarizing: