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.
|Original language||English (US)|
|Number of pages||17|
|State||Published - Mar 1 1990|
ASJC Scopus subject areas
- Algebra and Number Theory