Skip Navigation

Journal of Logic and Computation 1997 7(5):555-579; doi:10.1093/logcom/7.5.555
© 1997 by Oxford University Press
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by SACCÀ, D.
Right arrow Articles by ZANIOLO, C.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Original Articles

Deterministic and Non-deterministic Stable Models

DOMENICO SACCÀ1 and CARO ZANIOLO2

1Dipartimento DEIS, Università della Calabria 87030 Rende (CS), Italy. E-mail: sacca{at}unical.it
2Computer Science Department, University of California Los Angeles, CA 90024, USA. E-mail: zaniolo{at}cs.ucla.edu

Stable models have been first introduced in the domain of total interpretations (T-stable models), where the existence of multiple T-stable models for the same program provides a powerful mechanism to express non-determinism. Stable models have been later extended to the domain of partial interpretations (P-stable models). In this paper, we show that the presence of multiple P-stable models need not be a direct manifestation of non-determinism, for it can be instead an expression of assorted degrees of undefinedness. To separate the two factors, non-determinism and undefinedness, this paper introduces the notion of deterministic stable models and strictly non-deterministic ones. Deterministic stable models form an interesting family, having a lattice structure where the well-founded model serves as the bottom; the top of the lattice, the maximum deterministic stable model, resolves differences between any two P-stable models in the family. On the other hand, every two models in a family of strictly non-deterministic P-stable models have un-reconcilable differences, so that one must be chosen to the exclusion of the other. One such strictly non-deterministic family is constituted by the T-stable models. The paper characterizes two other interesting families: the maximal stable (M-stable) models (i.e. those not contained in any other P-stable model), and the least-undefined stable (L-stable) models (i.e. maximal stable models with the minimal set of undefined atoms). The paper studies the properties of models in these classes, and characterizes the computational complexity of finding the various types of stable models for DATALOG programs.

Keywords: Logic programming; stable models; non-deterministic semantics; DATALOG; data complexity


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.