The Differential Fixpoint of General Logic Programs.
Ulrich Zukowski, Burkhard Freitag · 1996
We present a version of the alternating fixpoint procedure that is fully incremental. Using ideas of partial evaluation techniques we can compute the well-founded model of logic programs with negation bottom-up without any recomputations. Further extensions of the semantics, e.g. to stable models or disjunctive programs are possible this way. We show how to implement the algorithm efficiently using index-based data structures and describe an extension to handle magic set transformed programs. This set-oriented bottomup algorithm is compatible with the well-known optimizations of deductive databases, e.g. semi-naive fixpoint iteration, and of relational databases, e.g. index techniques that enable the processing of large amounts of data. Thus, a bottom-up alternative to the already known efficient top-down methods for the well-founded semantics seems to be feasible. 1 Introduction A very influential and well-accepted semantics for logic programs with negation is the wellfounded semanti...