THE EXPRESSIVE POWERS OF STABLE MODELS FOR BOUND AND UNBOUND DATALOG QUERIES

Various types of stable models are known in the literature: T-stable ( total stable), P-stable ( partial stable, also called three-valued sta ble), M-stable (maximal stable, also known under Various different nam es), and L-stable ( least undefined stable). For each type of stable m odel, the paper analyzes two versions of deterministic semantics: poss ible semantics, which is based on the union of all stable models of th e given type, and definite semantics, which is instead based on their intersection and is like classical certain semantics except that it ma kes no inference if no model exists. For total stable models, which ar e the only type of stable models whose existence is not guaranteed for every program, certain semantics is taken into account as well. The e xpressive powers of each type of stable model under the above Versions of semantics are investigated for both bound (i.e., ground) and unbou nd queries on DATALOG programs with negation. As deterministic semanti cs is argued to be inappropriate for unbound queries, a non-determinis tic semantics is also proposed for them and its expressive power is fu lly characterized as well. (C) 1997 Academic Press.