A FIRST-ORDER REPRESENTATION OF STABLE MODELS

Turi (1991) introduced the important notion of a constrained atom: an atom with associated equality and disequality constraints on its argum ents. A set of constrained atoms is a constrained interpretation. We i nvestigate how non-ground representations of both the stable model sem antics and the well-founded semantics may be obtained through Turi's a pproach. The practical implication of this is that the well-founded mo del (or the set of stable models) may be partially pre-computed at com pile-time, resulting in the association of each predicate symbol in th e program to a constrained atom. Algorithms to create such models are presented, both for the well founded case, and the case of stable mode ls. Query processing reduces to checking whether each atom in the quer y is true in a stable model (resp. well-founded model). This amounts t o showing the atom is an instance of one of some constrained atom whos e associated constraint is solvable. Various related complexity result s are explored, and the impacts of these results are discussed from th e point of view of implementing systems that incorporate the stable an d well-founded semantics.