Arithmetic Classification of Perfect Models of Stratified Programs
Krzysztof Rafal Apt, Howard A. Blair · Fundamenta Informaticae · 1990
We study here the recursion theoretic complexity of the perfect (Herbrand) models of stratified logic programs. We show that these models lie arbitrarily high in the arithmetic hierarchy. As a byproduct we obtain a similar characterization of the recursion theoretic complexity of the set of consequences in a number of formalisms for non-monotonic reasoning. We show that under some circumstances this complexity can be brought down to recursive enumerability.