THE STABLE MODELS OF A PREDICATE LOGIC PROGRAM

We study the family of stable models of finite and recursive predicate logic programs. We show that the family of stable models of a recursi ve predicate logic program is, up to a recursive coding, a PI1(0) clas s (i.e. an effectively closed set) and, vice versa, that each PI1(0) c lass is, up to a recursive coding, the family of stable models of a fi nite predicate logic program. Since the structure of the Turing degree s of elements of PI1(0) classes has been extensively studied, these co ding results automatically imply many results about the degrees of sta ble models of finite predicate logic programs. For example, there exis ts a finite predicate logic program which has a stable model but which has no stable model which is hyperarithmetic and the existence proble m for stable models of finite predicate logic programs is a SIGMA1(1)- complete problem.