On Extended Disjunctive Logic Programs

Department of Computer Science
Institute for Advanced Computer Studies
University of Maryland, College Park, MD 20742, USA.
Jack Minker
Carolina Ruiz

The complete paper is available in:


This paper studies, in a comprehensive manner, different aspects of extended disjunctive logic programs, that is, programs whose clauses are of the form
l1 or ... or lk <-  lk+1,...,lm,not lm+1,...,not ln
where l1,...,ln are literals (i.e. atoms and classically negated atoms), and not is the negation-by-default operator. The explicit use of classical negation suggests the introduction of a new truth value, namely, logical falsehood (in contrast to falsehood-by-default) in the semantics. General techniques are described for extending the model, fixpoint, and proof theories of an arbitrary semantics of normal disjunctive logic programs to cover the class of extended programs. Illustrations of these techniques are given for stable models, disjunctive well-founded and stationary se- mantics. Also, the declarative complexity of the extended programs as well as the algorithmic complexity of the proof procedures are discussed.