Unifying abductive logic programming and stable logic programming

Abductive Logic Programming (ALP) and Answer Set Programming (ASP) were developed independently and are defined in terms of quite different foundations and concepts. Yet, the existence of formally proven relationships and the often striking congruence between application programs in both formalisms suggest that, at a deeper level, both formalisms might be tighly related. In this talk, I will take an epistemological viewpoint to investigate and uncover this relationship. Epistemological foundations of both formalisms can been defined in terms of two nonmonotonic reasoning principles, in particular autoepistemic/default reasoning on the one hand and iterated inductive definitions on the other hand. Both principles are fundamentally different, even contrary nonmonotonic principles, one being a minimising knowledge principle while the second being a mazimising knowledge principle. In the talk, I will argue that Answer Set Programming with two negations is an instance of the first principle whereas Abductive Logic Programming and Stable Logic Programming are instances of the second principle. Stable logic programming is thus presented as a fundamentally different logic than Answer Set Programming with two negations. This contradicts with the standard view in which Stable Logic Programming is viewed as a subformalism of ASP. I will back up my position with formal results showing that stable logic programming and ASP attribute fundamentally different modalities to the negation as failure operator and the rule operator. On the other hand, this work unifies Stable Logic Programming and Abductive Logic Programming as syntactic variants of the same underlying logic. The impact on methodology will be discussed. At the computational level, Abductive Logic Programming and Stable Logic Programming provide different computational approaches for essentially the same type of reasoning problem. During his invited talk at NMR2000, Victor Marek complained about the lack of relationship and the confused position of logic programming in the broader area of mathematical and philosophical logic. In this talk, a big step is made in clarifying the picture. At the same time, the talk addresses a number of fundamental logical ambiguities and long standing open problems about the meaning of language constructs such as negation as failure and rule operator in logic programming extensions.

Authors

• Marc Denecker

Keywords

No keywords are indexed for this paper.