Complexity of Nested Circumscription and Abnormality Theories
Abstract
We propose L Circ , 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 L Circ 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 L Circ resp. NATs as a host language for expressing other formalisms, such as narratives.
Cite
Text
Cadoli et al. "Complexity of Nested Circumscription and Abnormality Theories." International Joint Conference on Artificial Intelligence, 2001.Markdown
[Cadoli et al. "Complexity of Nested Circumscription and Abnormality Theories." International Joint Conference on Artificial Intelligence, 2001.](https://mlanthology.org/ijcai/2001/cadoli2001ijcai-complexity/)BibTeX
@inproceedings{cadoli2001ijcai-complexity,
title = {{Complexity of Nested Circumscription and Abnormality Theories}},
author = {Cadoli, Marco and Eiter, Thomas and Gottlob, Georg},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2001},
pages = {169-174},
url = {https://mlanthology.org/ijcai/2001/cadoli2001ijcai-complexity/}
}