XSB: A System for Efficiently Computing Well-Founded Semantics

Click on the title to obtain a gzip-ed PostScript version of the paper (43K).


The well-founded model provides a natural and robust semantics for logic programs with negative literals in rule bodies. We implemented the well-founded semantics in the SLG-WAM of XSB. Performance results indicate that the overhead of delay and simplification to Prolog -- or tabled -- evaluations is minimal. To compute the well-founded semantics, the SLG-WAM adds to an efficient tabling engine for definite programs three operations -- negative loop detection, delay and simplification -- which serve to detect, to break and to resolve cycles through negation that might arise in evaluating normal programs.

XSB is a full Prolog system that closely approximates the ISO standard; additionally, it supports a tight integration of tabled predicates with nontabled predicates.