AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
Defeasible Inclusions in Low-Complexity DLs: Preliminary Notes
Piero A. Bonatti, Marco Faella, Luigi Sauro

Last modified: 2009-06-25


We analyze the complexity of reasoning with circumscribed low-complexity DLs such as DL-lite and the EL family, under suitable restrictions on the use of abnormality predicates. We prove that in circumscribed DL-liteR complexity drops from NExpNP to the second level of the polynomial hierarchy. In EL, reasoning remains ExpTime-hard, in general. However, by restricting the possible occurrences of existential restrictions, we obtain membership in Sigmap2 and Pip2 for an extension of EL.


Description logics; circumscription

Full Text: PDF