Understanding Negation in Logic Programming

The use of explicit negation enhances the expressive power of logic programs by providing a natural and unambiguous way to assert negated information about the domain being represented. We study the semantics of disjunctive programs that contain both explicit negation and negation-by-default, called extended disjunctive logic programs. We have described general techniques for extending model, fixpoint, and proof theoretic characterizations of an arbitrary semantics of normal disjunctive logic programs to cover the class of extended programs, and have given illustrations of these techniques for stable models, minimal Herbrand models, disjunctive well-founded and stationary semantics. In addition, we have studied the declarative complexity of the extended programs, as well as the algorithmic complexity of the proof procedures and fixpoint operators. Currently, we are investigating the semantics of disjunctive logic programs containing several kinds of default negation in addition to explicit.


Publications available on-line: