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

Georg Gottlob*, Sherry Marcus, Anil Nerode, Gernot Salzer, V. S. Subrahmanian

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)221-262
Number of pages42
JournalTheoretical Computer Science
Volume166
Issue number1-2
DOIs
StatePublished - Oct 20 1996
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'A non-ground realization of the stable and well-founded semantics'. Together they form a unique fingerprint.

Cite this