Principles and properties of declarative programming with answer sets
Chitta Baral · Cambridge University Press eBooks · 2003
In this chapter we present several fundamental results that are useful in analyzing and step-by-step building of AnsProlog * Programs, viewed both as stand alone programs and as functions. To analyze AnsProlog * programs we define and describe several properties such as categoricity (presence of unique answer sets), coherence (presence of at least one answer set), computability (answer set computation being recursive), filter-abducibility (abductive assimilation of observations using filtering), language independence (independence between answer sets of a program and the language), language tolerance (preservation of the meaning of a program with respect to the original language when the language is enlarged), compilabity to first-order theory, amenabity to removal of or , and restricted monotonicity (exhibition of monotonicity with respect to a select set of literals). We also define several subclasses of AnsProlog * programs such as stratified, locally stratified, acyclic, tight, signed, head cycle free and several conditions on AnsProlog * rules such as well-moded and state results about which AnsProlog * programs have what properties. We present several results that relate answer sets of an AnsProlog * program to its rules. We develop the notion of splitting and show how the notions of stratification, local stratification, and splitting can be used in step-by-step computation of answer sets. For step-by-step building of AnsProlog * programs we develop the notion of conservative extension – where a program preserves its original meaning after additional rules are added to it, and present conditions for programs that exhibit this property.