Some Computational Aspects of Circumscription

Phokion G. Kolaitis, Christos H. Papadimitriou

Abstract

The effects of circumscribing first-order formulas are explored from a computational standpoint. First, extending work of V. Lifschitz, it is Shown that the circumscription of any existential first-order formula is equivalent to a first-order formula. After this, it is established that a set of universal Horn clauses has a first-order circumscription if and only if it is bounded (when considered as a logic program); thus it is undecidable to tell whether such formulas have first-order circumscription. Finally, it is shown that there arefirst-order formulas whode circumscription has a coNP-complete model-checking problem.
BibTeX
@inproceedings{kolaitis1988some,
  author = {Phokion G. Kolaitis and Christos H. Papadimitriou},
  title = {{Some Computational Aspects of Circumscription}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}

Loading related content...

Figure