TY - JOUR

T1 - A non-ground realization of the stable and well-founded semantics

AU - Gottlob, Georg

AU - Marcus, Sherry

AU - Nerode, Anil

AU - Salzer, Gernot

AU - Subrahmanian, V. S.

N1 - Funding Information:
* Corresponding author. E-mail: gottlob@vexpert.dbai.tuwien.ac.at. t G. Gottlob's and G. Salzer's research was supported by the Christian Doppler Lab. The other authors were supported by the Army Research Office under grants DAAG-29-85-C-0018 and DAAL-03-92-G-0225, by the Air Force Office of Scientific Research under Grant Nr. F49620-93-1-0065 and by NSF grants IRI-91-09755 and IRI-93-57756.

PY - 1996/10/20

Y1 - 1996/10/20

N2 - The declarative semantics of nonmonotonic logic programming has largely been based on propositional programs. However, the ground instantiation of a logic program may be very large, and likewise, a ground stable model may also be very large. We develop a non-ground semantic theory for non-monotonic logic programming. Its principal advantage is that stable models and well-founded models can be represented as sets of atoms, rather than as sets of ground atoms. A set SI of atoms may be viewed as a compact representation of the Herbrand interpretation consisting of all ground instances of atoms in SI. We develop generalizations of the stable and well-founded semantics based on such non-ground interpretations SI. The key notions for our theory are those of covers and anticovers. A cover as well as its anticover are sets of substitutions - non-ground in general - representing all substitutions obtained by ground instantiating some substitution in the (anti)cover, with the additional requirement that each ground substitution is represented either by the cover or by the anticover, but not by both. We develop methods for computing anticovers for a given cover, show that membership in so-called optimal covers is decidable, and investigate the complexity in the Datalog case.

AB - The declarative semantics of nonmonotonic logic programming has largely been based on propositional programs. However, the ground instantiation of a logic program may be very large, and likewise, a ground stable model may also be very large. We develop a non-ground semantic theory for non-monotonic logic programming. Its principal advantage is that stable models and well-founded models can be represented as sets of atoms, rather than as sets of ground atoms. A set SI of atoms may be viewed as a compact representation of the Herbrand interpretation consisting of all ground instances of atoms in SI. We develop generalizations of the stable and well-founded semantics based on such non-ground interpretations SI. The key notions for our theory are those of covers and anticovers. A cover as well as its anticover are sets of substitutions - non-ground in general - representing all substitutions obtained by ground instantiating some substitution in the (anti)cover, with the additional requirement that each ground substitution is represented either by the cover or by the anticover, but not by both. We develop methods for computing anticovers for a given cover, show that membership in so-called optimal covers is decidable, and investigate the complexity in the Datalog case.

UR - http://www.scopus.com/inward/record.url?scp=0030257465&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030257465&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(95)00207-3

DO - 10.1016/0304-3975(95)00207-3

M3 - Article

AN - SCOPUS:0030257465

SN - 0304-3975

VL - 166

SP - 221

EP - 262

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -