On Positive Occurrences of Negation as Failure
Katsumi Inoue and Chiaki Sakama
Proceedings of the 4th International Conference on
Principles of Knowledge Representation and Reasoning (KR'94),
pp. 293-304, Morgan Kaufmann Publishers, 1994.
Abstract
Logic programs with positive occurrences of negation as failure
have recently been introduced as a subset of the logic of
minimal belief and negation as failure (MBNF).
A unique feature of such programs,
which other traditional logic programs lack,
is that the minimality of answer sets does not hold.
We reveal in this paper that this property is important
for applying logic programming to represent abduction
and inclusive disjunctions.
With its rich expressiveness, however, the computational complexity
of such extended programs is shown to remain in the same complexity class
as normal disjunctive programs. Through the elimination of
negation as failure from programs, computation of such extended programs
is realized using bottom-up model generation techniques.
A simple translation of programs into autoepistemic logic is also presented.
Full Paper (pdf 330K)