Well-founded ordered search: Goal-directed bottom-up evaluation of well-founded models

Abstract

There have been several evaluation mechanisms proposed for computing query answers based on the well-founded semantics, for programs with negation. However, these techniques are costly; in particular, for the special case of modularly stratified programs, Ordered Search is more efficient than the general-purpose techniques. However, Ordered Search is applicable only to modularly stratified programs. In this paper, we extend Ordered Search to compute the well-founded semantics for all (non-floundering) programs with negation. Our extension behaves exactly like Ordered Search on programs that are modularly stratified, and hence pays no extra cost for such programs.