Eliminating negation from normal logic programs

Abstract

In this paper, we propose a bottom-up partial evaluation of normal programs with a topdown expansion of negated atoms to obtain equivalent logic programs. A program P is transformed to Pω by a bottom-up computation on the positive component of P while the negative counterpart is left untouched. During this process, we collect all substitutions describing a partial answer set to all the positive atoms in the bodies of P. The declarative semantics of P is given by the completion of Pω. The completed predicate definitions in Pω if they do not contain local variables, can be used as a basis for expanding each negated atom in the bodies of Pω. We show that for a class of programs where every nega..