WELL-FOUNDED ORDERED SEARCH - GOAL-DIRECTED BOTTOM-UP EVALUATION OF WELL-FOUNDED MODELS

There have been several evaluation mechanisms proposed for computing q uery answers based on the well-founded semantics, for programs with ne gation. However, these techniques are costly; in particular, for the s pecial case of modularly stratified programs, Ordered Search is more e fficient 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 he nce pays no extra cost for such programs. (C) Elsevier Science Inc., 1 997.