Fundamenta informaticae on Logic Programming
Krzysztof Rafal Apt · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 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. 1990, Polish Mathematical Society Biblrorrre&I Am!"ff"r'111rr.