Autoepistemic answer set programming

摘要

Defined by Gelfond in 1991, epistemic specifications constitute an extension of Answer Set Programming (ASP) that introduces subjective literals. A subjective literal allows checking whether some regular literal is true in all (or in some of) the answer sets of the program, that are further collected in a set called world view. One epistemic program may yield several world views but, under the original semantics, some of them resulted from self-supported derivations. During the last eight years, several alternative approaches have been proposed to get rid of these self-supported world views. Unfortunately, their success could only be measured by studying their behaviour on a set of common examples in the literature, since no formal property of “self-supportedness” had been defined. To fill this gap, we extend in this paper the idea of unfounded set from standard logic programming to the epistemic case. We define when a world view is founded with respect to some program. Accordingly, we define the foundedness property for an arbitrary semantics, so it holds when its world views are always founded. Using counterexamples, we explain that the previous approaches violate foundedness, and proceed to propose a new semantics based on a combination of Moore's Autoepistemic Logic and Pearce's Equilibrium Logic. This combination paves the way for the development of an autoepistemic extension of ASP. The main result proves that this new semantics precisely captures the set of world views of the original semantics that are founded.