Some Computational Aspects of Circumscription
Lists
Only you see this
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...