Volume 7: January - December 1997

Issue 5: October 1997


Deterministic and non-deterministic stable models

  • Deterministic and non-deterministic stable models
  • D. Sacca and C. Zaniolo1

    Dipartimento DEIS, Universita della Calabria, 87030 Rende (CS), Italy. E-mail: sacca@unical.it and 1Computer Science Department, University of California, Los Angeles, CA 90024, USA. E-mail: zaniolo@cs.ucla.edu


    Stable models have been first introduced in the domain of total (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 unreconcilable 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.

    Pages: 555 - 579

    Part of the OUP Journal of Logic and Computation WWW service

    General Information

    Click here to register with OUP.

    This page is maintained by OUP admin

    Part of the OUP Journals World Wide Web service.

    Last modification: 24 Oct 1997

    Copyright© Oxford University Press, 1997.