Computing non-ground representations of stable models

Thomas Eiter, James Lu, V. S. Subrahmanian

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

Turi [20] introduced the important notion of a constrained atom: an atom with associated equality and disequality constraints on its arguments. A set of constrained atoms is a constrained interpretation. We show how non-ground representations of both the stable model and the well-founded semantics may be obtained through Turi’s approach. As a practical consequence, the well-founded model (or the set of stable models) may be partially pre-computed at compile-time, resulting in the association of each predicate symbol in the program to a constrained atom. Algorithms to create such models are presented. Query processing reduces to checking whether each atom in the query is true in a stable model (resp. well-founded model). This amounts to showing the atom is an instance of one of some constrained atom whose associated constraint is solvable. Various related complexity results are explored, and the impacts of these results are discussed from the point of view of implementing systems that incorporate the stable and well-founded semantics.

Original languageEnglish (US)
Title of host publicationLogic Programming and Nonmonotonic Reasoning - 4th International Conference, LPNMR 1997, Proceedings
EditorsJurgen Dix, Ulrich Furbach, Anil Nerode
PublisherSpringer Verlag
Pages198-217
Number of pages20
ISBN (Print)9783540632559
DOIs
StatePublished - 1997
Externally publishedYes
Event4th International Conference on Logic Programming and Non-Monotonic Reasoning, LPNMR 1997 - Dagstuhl Castle, Germany
Duration: Jul 28 1997Jul 31 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1265
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Conference on Logic Programming and Non-Monotonic Reasoning, LPNMR 1997
Country/TerritoryGermany
CityDagstuhl Castle
Period7/28/977/31/97

Keywords

  • Algorithms
  • Complexity
  • Constraints
  • Non-ground representation
  • Stable models

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Computing non-ground representations of stable models'. Together they form a unique fingerprint.

Cite this