Arithmetic classification of perfect models of stratified programs

K. R. Apt, H. A. Blair

Research output: Contribution to journalArticle

38 Scopus citations

Abstract

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 languageEnglish (US)
Pages (from-to)1-17
Number of pages17
JournalFundamenta Mathematicae
Volume13
Issue number1
StatePublished - Mar 1 1990

ASJC Scopus subject areas

  • Algebra and Number Theory

Fingerprint Dive into the research topics of 'Arithmetic classification of perfect models of stratified programs'. Together they form a unique fingerprint.

  • Cite this