In this survey paper, the reader is guided through a number of different fixpoint-based semantics, ranging from the usual Apt-van Emden-Kowalski semantics to metric approaches, and also considering the stable models semantics. As stated in the introduction, only developments that have been of interest to the author are surveyed, but this is nevertheless a thorough and interesting presentation of the use of fixpoint theory in logic programming.
Once the classical semantics of logic programs have been introduced, the “revision operator” TP is defined, in order to present the Apt-van Emden-Kowalski semantics. The use of Horn clauses makes the TP operator monotone, and then, by the Knaster-Tarski theorem, both the smallest and largest fixed points exist.
With the introduction of negation, the TP is no longer monotone, and as a result, the whole semantics has to be modified. The Kripke-Kleene semantics is proposed, with three-valued semantics and a generalization &PHgr;P of the TP operator to handle the extra truth-value. This approach maintains the existence of smallest fixed points, coinciding with the result given by the previous approach in the case of definite programs, but largest fixed points need not exist.
The use of more than two truth values suggests the possibility of applying sets of truth values that are both more general and have suitable algebraic properties. The first candidate is Belnap’s four-valued logic, where one can recover the existence of the largest fixed point, based on considering ⊥ as the default value instead of false. The introduction of stable model semantics allows restoration of the original situation. After presenting the original two-valued approach by Gelfond-Lifschitz, the three-valued generalization by Przymusinski is introduced. The author describes this approach directly in four-valued logic, since in this context it is easier to extract the algebraic features of the different approaches introduced so far.
The final sections are devoted to the generalization of the previous approach to use the more general concept of bilattice, thoroughly studied by Ginsberg, and the use of the metric approach, which substitutes the use of the Knaster-Tarski theorem with the Banach contraction theorem.