Well-founded ordered search

Abstract

There have been several evaluation mechanisms proposed for computing query answers based on the well-founded semantics, for progrants with negation. However, these techniques are costly; in particular, for the special case of modularly stratified programs Ordered Search is more efficient titan 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.