Deterministic and non-deterministic stable models

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.