Arithmetic Classification of Perfect Models of Stratified Programs

摘要

The recursion theoretic complexity of the perfect (Herbrand) models of stratified logic programs is studied. It is shown that these models lie arbitrarily high in the arithmetic hierarchy. A byproduct is a similar characterization of the recursion theoretic complexity of the set of consequences in a number of formalisms for nonmonotonic reasoning. Under some circumstances this complexity can be brought down to recursive enumerability.