Stable models and their computation for logic programming with inheritance and true negation

Previous researchers have proposed extensions of logic programming to deal with true negation and defeasible reasoning. Ordered Logic (OC) achieves both such goals by allowing rules with negated heads in the context of an inheritance hierarchy. As a result, OL is inherently nonmonotonic. Another area of interest in logic programming is that dealing with the semantics of negation. Recent research focuses on both declarative and constructive characterizations of stable models. A peculiarity of this semantics is that a program may have several alternative models (even none), each corresponding to a possible view of the world. This endows logic programming with the power to express don't-care nondeterminism in a purely declarative framework. This paper describes a stable model semantics (SMS(OL)) and its computation for ordered logic programs. SMS(OL) is given both in a model-theoretic and a constructive fashion. Based on the latter, an effective method is proposed for computing OC stable models. An interesting aspect of the proposed approach is that ordered logic programming can simulate Datalog under the total stable model semantics. This clearly provides solidity to our proposal. Moreover, the SMS(OL) computation method is an effective way to compute the stable model semantics of Datalog programs. The computational complexity of the main reasoning tasks in SMS(OL) is also investigated.