A topological characterization of the stable and minimal model classes of propositional logic programs

Abstract

In terms of the arithmetic hierarchy, the complexity of the set of minimal models and of the set of stable models of a propositional general logic program has previously been described. However, not every set of interpretations of this level of complexity is obtained as such a set. In this paper we identify the sets of interpretations which are minimal or stable model classes by their properties in an appropriate topology on the space of interpretations. Closely connected with the topological characterization, in parallel with results previously known for stable model classes we obtain for minimal model classes both a normal-form representation as the set of minimal models of a prerequisite-free program and a logical description in terms of formulas. Our approach centers on the relation which we establish between stable and minimal model classes. We include examples of calculations which can be performed by these methods.