Complexity of Nested Circumscription and Abnormality Theories
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 169-173.
Abstract
We propose an extension of circumscription by allowing propositional combinations and nesting of circumscriptive theories. As shown, Lifschitz’s nested abnormality theories (NATs, introduced in AIJ, 1995) are naturally embedded into this language. We analyze the complexity of and NATs, and in particular the effect of nesting. The latter is found a source of complexity, as both formalisms are proved to be PSPACE-complete. We identify cases of lower complexity, including a tractable case. Our results give insight into the “cost” of using resp. NATs as a host language for expressing other formalisms, such as narratives.
@inproceedings{ijcai2001p23,
title = {Complexity of Nested Circumscription and Abnormality Theories},
author = {Cadoli, Marco and Eiter, Thomas and Gottlob, Georg},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {169--173},
year = {2001},
url = {https://ijcai.org/proceedings/2001/23},
}
TY - CPAPER TI - Complexity of Nested Circumscription and Abnormality Theories AU - Cadoli, Marco AU - Eiter, Thomas AU - Gottlob, Georg T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 169 EP - 173 UR - https://ijcai.org/proceedings/2001/23 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
