---
title: "Complexity of Nested Circumscription and Abnormality Theories"
authors:
  - "Marco Cadoli"
  - "Thomas Eiter"
  - "Georg Gottlob"
doi: ""
url: "https://ijcai.org/proceedings/2001/23"
pdf: "https://ijcai.org/proceedings/2001/0023.pdf"
venue: "Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence"
year: 2001
pages: "169-173"
track: ""
keywords:
---

# Complexity of Nested Circumscription and Abnormality Theories

Marco Cadoli, Thomas Eiter, Georg Gottlob

*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.