zbMATH — the first resource for mathematics

A classification theory of semantics of normal logic programs. I: Strong properties. (English) Zbl 0829.68021
Summary: Our aim in this article is to present a method for classifying and characterizing the various different semantics of logic programs with negation that have been considered in the last years. Instead of appealing to more or less questionable intuitions, we take a more structural view: our starting point is the observation that all semantics induce in a natural way non-monotonic entailment relations “\(\mid \sim\)”. The novel idea of our approach is to ask for the properties of these \(\mid \sim\)-relations and to use them for describing all possible semantics. The main properties discussed in this paper are adaptions of rules that play a fundamental rôle in general nonmonotonic reasoning: Cumulativity and Rationality. They were introduced and investigated by Gabbay, Kraus, Lehmann, Magidor and Makinson. We show that the 3-valued version \(\text{COMP}_3\) of Clark’s completion, the stratified semantics \(M_P^{\text{supp}}\) as well as the well-founded semantics WFS and two extensions of it behave very regular: they are cumulative, rational and one of them is even supraclassical. While Pereira’s recently proposed semantics O-SEM is not rational it is still cumulative. Cumulativity fails for the regular semantics REG-SEM of You/Yuan (recently shown to be equivalent to three other proposals). In a second article we will supplement these strong rules with a set of weak rules and consider the problem of uniquely describing a given semantics by its strong and weak properties together.

68N17 Logic programming
68Q55 Semantics in the theory of computing