A Rational Extension of Stable Model Semantics to the Full Propositional Language

Abstract

Answer set programming is the most appreciated framework for non-monotonic reasoning. Stable model semantics, as the semantics behind this success, has been subject to many extensions. The two main such extensions are equilibrium models and FLP semantics. Despite their very interesting foundations, they both have two problems: they cannot guarantee either minimality, or rationality of their intended models. That is, both these semantics allow models in which some atoms are self-justified (i.e., the only possible reason for including those atoms in the model are those atoms themselves). Present paper extends stable model semantics to the full propositional language while guaranteeing both properties above. Our extension is called supported because it guarantees the existence of non-circular justifications for all atoms in a supported model. These goals are achieved through a form of completion in intuitionistic logic. We also discuss how supported models relate to other semantics for non-monotonic reasoning such as equilibrium models. Finally, we discuss the complexity of reasoning about supported models and show that the complexity of brave/cautious reasoning in supported semantics remains as before, i.e., the rationality property comes for no additional cost.