3 - Principles and properties of declarative programming with answer sets

Summary

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.