Computer Science – Artificial Intelligence
Scientific paper
2002-07-20
Computer Science
Artificial Intelligence
A preliminary abstract of this paper appeared in Proc. Seventeenth International Joint Conference on Artificial Intelligence (
Scientific paper
The need for a circumscriptive formalism that allows for simple yet elegant modular problem representation has led Lifschitz (AIJ, 1995) to introduce nested abnormality theories (NATs) as a tool for modular knowledge representation, tailored for applying circumscription to minimize exceptional circumstances. Abstracting from this particular objective, we propose L_{CIRC}, which is an extension of generic propositional circumscription by allowing propositional combinations and nesting of circumscriptive theories. As shown, NATs are naturally embedded into this language, and are in fact of equal expressive capability. We then analyze the complexity of L_{CIRC} and NATs, and in particular the effect of nesting. The latter is found to be a source of complexity, which climbs the Polynomial Hierarchy as the nesting depth increases and reaches PSPACE-completeness in the general case. We also identify meaningful syntactic fragments of NATs which have lower complexity. In particular, we show that the generalization of Horn circumscription in the NAT framework remains CONP-complete, and that Horn NATs without fixed letters can be efficiently transformed into an equivalent Horn CNF, which implies polynomial solvability of principal reasoning tasks. Finally, we also study extensions of NATs and briefly address the complexity in the first-order case. Our results give insight into the ``cost'' of using L_{CIRC} (resp. NATs) as a host language for expressing other formalisms such as action theories, narratives, or spatial theories.
Cadoli Marco
Eiter Thomas
Gottlob Georg
No associations
LandOfFree
Complexity of Nested Circumscription and Nested Abnormality Theories does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Complexity of Nested Circumscription and Nested Abnormality Theories, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Nested Circumscription and Nested Abnormality Theories will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-541272