This paper is concerned with the axiomatization of success and failure in propositional logic programming. It deals with the actual implementation of SLDNF in PROLOG, as opposed to the general nondeterministic SLDNF evaluation method. Given any propositional program P, a linear theory LT, is defined (the linear translation of PI and the following results are proved for any literal A: soundness of PROLOG evuhation (if the goal A PROLOG-succeeds on P, then LT, kli,, A, and if A PROLOG-fails on P, then LT, I-,~" Al), and completeness of PROLOG evaluation (if LT, I-,~" A, then the goal A PROLOG-succeeds on P, and if LT, +,in A' , then A PROLOG-fails on PI. Here l-,in means provability in linear logic, and Al is the linear negation of A. a INTRODUCTION This paper is concerned with the axiomatization of success and failure in propositional logic programming. One wants to prove something like A succeeds iff A is provable, A fails iff the negation of A is provable, where "provable" means provable in a certain theory TMP) depending on the program P that we are considering. A basic choice has to be made: either (i) we decide-as in most of the literature (see [ll] for a general reference)-to axiomatize the general SLDNF method (or a variant of it, as for example the algorithm studied in 116]), or (ii) we decide to treat the implemented version of SLDNF, i.e. PROLOG.
In REF , a translation from a propositional Prolog program P to a linear logic theory LTp is given, and the soundness and completeness of the translation is proved: the goal A succeeds under the Prolog evaluation iff LTp I"tin A, and A fails iff LTp ~-Iin A • 9
A linear axiomatization of negation as failure
J. Log. Program.
J. Log. Program.
Mathematics Computer Science