Refining Gelfond’s Rationality Principle: Towards More Comprehensive Foundational Principles for Answer Set Semantics

Abstract

Non-monotonic logic programming is the basis for a declarative problem solving paradigm known as answer set programming (ASP), where solutions to problems are encoded by intended models (answer sets) of a logic program. Departing from the seminal definition by Gelfond and Lifschitz [45] for simple normal logic programs, various answer set semantics have been proposed for extensions such as disjunctive logic programs and epistemic logic programs. In the latter case, the semantics consists of sets of answer sets called world views. In general, it seems infeasible to formally prove whether a proposal defines answer sets/world views that correspond exactly to the solutions of any problem intuitively represented by a logic program. It is thus necessary to develop some general principles and use them as a baseline to intuitively compare and assess different answer set and world view semantics, respectively. Towards such a baseline, we consider two important questions: (1) Should the minimal model property, constraint monotonicity and foundedness as defined in the literature be mandatory conditions for an answer set semantics in general? (2) If not, what other properties could be considered as alternative principles for answer set semantics? We address the two questions with several contributions. First, we use examples to demonstrate that requiring minimal models, constraint monotonicity and foundedness as mandatory conditions may exclude expected answer sets for some simple disjunctive programs and world views for some epistemic specifications. Second, we evolve the Gelfond answer set (GAS) principles [42] for answer set construction by refining the Gelfond's rationality principle to well-supportedness, minimality w.r.t. negation by default, and minimality w.r.t. epistemic negation. The principle of well-supportedness guarantees that every answer set is constructible from if-then rules obeying a level mapping and is thus free of circular justification, while the two minimality principles ensure that the formalism minimizes knowledge both at the level of answer sets and of world views. We thus propose to consider the three refined GAS principles as alternative principles for answer set semantics in general and for answer set and world view construction in particular. Third, to embody the refined GAS principles, we extend the notion of well-supportedness substantially to answer sets and world views, respectively. Fourth, we propose to define answer set semantics in terms of the refined GAS principles, called rational answer set and rational world view semantics, respectively. Fifth, we use the refined GAS principles as an alternative baseline to intuitively assess the existing answer set semantics whether they satisfy (are compliant with) or even fully embody the refined GAS principles. Finally, we analyze the computational complexity of well-supportedness and the rational answer set and world view semantics, revealing them as expressive hosts for problem solving.