7 - Answer set computing algorithms

Summary

In this chapter we discuss four algorithms for computing answer sets of ground AnsProlog^* programs. The first three algorithms compute answer sets of ground AnsProlog programs while the fourth algorithm computes answer sets of ground AnsProlog^or programs. In Chapter 8 we will discuss several implemented systems that compute answer sets and use algorithms from this chapter.

Recall that for ground AnsProlog and AnsProlog^or programs π answer sets are finite sets of atoms and are subsets of HBM_π. In other words answer sets are particular (Herbrand) interpretations of π which satisfy additional properties. Intuitively, for an answer set A of π all atoms in A are viewed as true with respect to A, and all atoms not in A are viewed as false with respect to A. Most answer set computing algorithms – including the algorithms in this chapter – search in the space of partial interpretations, where in a partial interpretation some atoms have the truth value true, some others have the truth value false and the remaining are considered to be neither true nor false. In the first three algorithms in this chapter the partial interpretations are 3-valued and are referred to as 3-valued interpretations, while in the fourth algorithm the partial interpretation that is used is 4-valued. Recall that we introduced 3-valued interpretations in Section 6.6.9, and that in 3-valued interpretations the atoms which are neither true not false have the truth value unknown.