We propose L_(Circ), an extension of circumscription by allowing propositional combinations and nesting of circumscriptive theories. As shown, Lifs-chitz'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.
展开▼
