A Comparison of Notions of Negation as Failure

Abstract When logic programming was generalized to allow negative subgoals, difficulties immediately arose concerning the meaning of negation as failure in the context of these subgoals. Various semantics have been proposed, each attempting to capture natural intuitions about negation as failure and to preserve other intuitive properties. We discuss several such semantics for normal logic programs here: the minimal model semantics, the perfect model semantics for stratified programs, the two- and three-valued program completion semantics, and the stable and well-founded semantics. We contrast them in various ways: we present some examples and intuitions that might be used to justify them, discuss which violate or preserve certain properties of more classical logics and which allow modular programming, and present some results about expressive powers and computational complexity.