Assumption-free Semantics for Ordered Logic Programs: On the Relationship Between Well-founded and Stable Partial Models

Abstract

Ordered logic programming is an extension of logic programming that includes, besides classical inference mechanisms, object-oriented abstractions and amenities for non- monotonic reasoning. Ordered logic programs are partially-ordered sets of ‘traditional’ logic programs where negation may also occur in the rule heads. The central issue of this paper is the definition of a new unifying semantics for ordered logic programs, called assumption-free semantics, capable of capturing different interesting semantics such as the well-founded and stable (partial model) semantics. It turns out that every ordered logic program possesses exactly one minimal assumption-free partial model which we call the well-founded partial model and one or more maximal assumption-free partial models called stable partial models. This stable model semantics can be viewed as taking the best of the previous approaches for ordered logic programs while keeping their (common) underlying intuition. We discuss the relationship between stable and well-founded partial models, the main result being that the intersection of all stable partial models is exactly the well-founded partial model in all cases but a special type of ordered logic programs.