Answer set computing algorithms
Chitta R. Baral · Cambridge University Press eBooks · 2003
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 .