Paper: How Uncomputable is General Circumscription? (Extended Abstract) (at LICS 1986)

Authors: John S. Schlipf

Abstract

We consider McCarthy's predicate and formula circumscription. We study the complexity of deciding whether a formula has an infinite minimal model and whether one formula holds in every infinite minimal model of another. We also ask what sets of integers are first order definable in all minimal models of a theory. For countably infinite models, the classes defined turn out to be familiar classes of generalized recursion theory, the same classes for both forms of circumscription. For arbitrary infinite models, even the exiistence of minimal models can be dependent upon the continuum hypothesis.

BibTeX

  @InProceedings{Schlipf-HowUncomputableisGe,
    author = 	 {John S. Schlipf},
    title = 	 {How Uncomputable is General Circumscription? (Extended Abstract)},
    booktitle =  {Proceedings of the First Annual IEEE Symposium on Logic in Computer Science (LICS 1986)},
    year =	 {1986},
    month =	 {June}, 
    pages =      {92--95},
    location =   {Cambridge, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }