Properties of Stable Model Semantics Extensions

ABSTRACT. The stable model (SM) semantics lacks the properties of existence, relevance and cumulativity. This is due to the set of SM models being generally smaller than the set of all minimum models of a normal logic program (the semantics that consists in all the minimal models of a normal logic program, let it be SEMmin, trivially verifies these three properties). If we prospectively consider the class of conservative extensions of SM semantics (i.e., semantics that for each normal logic program P retrieve a superset of the set of stable models of P), other than the trivial SEMmin, one may wander how do the semantics of this class behave in what concerns the aforementioned properties. That is the type of issue we deal with in this paper. We define a large class of conservative extensions of the SM semantics, dubbed affix stable model semantics, ASM, and study the above referred properties into two non-disjoint subfamilies of the class ASM, here dubbed ASMh and ASMm. From this study a number of results stem which facilitate the assessment of semantics in the class ASMh ∪ASMm with respect to the properties of existence, relevance and cumulativity, whilst unveiling relations among these properties. The following results should be emphasized: (1) We present a refined definition of cumulativity for semantics of in the class ASMh ∪ ASMm, which turns into an easier job the dismissal of this property by resorting to counter-examples; (2) We divide the sets of rules of normal logic programs into layers, and use the decomposition of models into that layered structure to define three new (structural) properties, defectivity, excessiveness and irregularity, which allow to state a number of relations between the properties of existence, relevance and cumulativity for semantics of the ASMh ∪ ASMm class, and at the same time facilitate the assessment of semantics in this class with respect to those properties; (3) As a result of the approach in our work light is shed on the characterization of the SM semantics, as we show that the properties of (lack of) existence and (lack of) cautious monotony are equivalent, which opposes statements on this issue that may be found in the literature; we also characterize the relevance failure of SM semantics in a more clear way than usually stated in the literature.