Negation as Failure in the Head
Katsumi Inoue and Chiaki Sakama
Journal of Logic Programming 35:39-78, North-Holland, 1998.
Abstract
The class of logic programs with negation as failure in the head
is a subset of the logic of MBNF introduced by Lifschitz
and is an extension of the class of extended disjunctive programs.
An interesting feature of such programs is that
the minimality of answer sets does not hold.
This paper considers the class of general extended disjunctive
programs (GEDPs) as logic programs with negation as failure in the head.
First, we discuss that the class of GEDPs is useful for
representing knowledge in various domains in which
the principle of minimality is too strong.
In particular, the class of abductive programs is properly included
in the class of GEDPs.
Other applications include the representation of inclusive disjunctions
and circumscription with fixed predicates.
Secondly, the semantic nature of GEDPs is analyzed by the syntax of programs.
In acyclic programs, negation as failure in the head can be shifted
to the body without changing the answer sets of the program.
On the other hand, supported sets of any program are always preserved
by the same transformation.
Thirdly, the computational complexity of the class of GEDPs is shown to
remain in the same complexity class as normal disjunctive programs.
Through the simulation of negation as failure in the head,
computation of answer sets and supported sets is realized
using any proof procedure for extended or positive disjunctive programs.
Finally, a simple translation of GEDPs into autoepistemic logic is presented.
Full Paper (pdf 2282K)