Skip to main content

A first-order representation of stable models1A preliminary version of this paper has appeared in: Proc. 4th International Conference on Logic Programming and Nonmonotonic Reasoning LPNMR '97, J. Dix, U. Furbach and A. Nerode, eds, LNCS 1265, Springer, 1997.

Buy Article:

$30.69 plus tax (Refund Policy)


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.

Keywords: Stable models; automated reasoning; compact representation

Document Type: Research Article

Affiliations: 1: Institut fur Informatik, Universitat Gieszen, Arndtstrasze 2, D-35392 Gieszen, Germany E-mail: 2: Department of Computer Science, Bucknell University, Lewisburg, PA, USA E-mail: 3: Institute for Advanced Computer Studies, Institute for Systems Research and Department of Computer Science, University of Maryland, College Park, MD 20742, USA E-mail:

Publication date: January 1, 1998


Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
Cookie Policy
ingentaconnect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more
Real Time Web Analytics