Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

A first-order representation of stable models

Eiter, Thomas ; Lu, James ; Subrahmanian, V.S


Zum Volltext im pdf-Format: Dokument 1.pdf (361 KB)


Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-306
URL: http://geb.uni-giessen.de/geb/volltexte/1998/30/


Universität Justus-Liebig-Universit√§t Gie√üen
Institut: Institut f√ľr Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 9805 / 1998
Sprache: Englisch
Erstellungsjahr: 1998
Publikationsdatum: 14.07.1998
Kurzfassung auf Deutsch: Turi (1991) 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 investigate how non­ground representations of both the stable model semantics and the well­founded semantics may be obtained through Turi's approach. The practical implication of this is that 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, both for the well founded case, and the case of stable models. 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.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand