On the Complexity of Dealing with Inconsistency in Description Logic Ontologies

Abstract

We study the problem of dealing with inconsistency in Description Logic (DL) ontologies. We consider inconsistency-tolerant semantics recently proposed in the literature, called AR-semantics and CAR-semantics, which are based on repairing (i.e., modifying) in a minimal way the extensional knowledge (ABox) while keeping the intensional knowledge (TBox) untouched. We study instance checking and conjunctive query entailment under the above inconsistency-tolerant semantics for a wide spectrum of DLs, ranging from tractable ones (EL) to very expressive ones (SHIQ), showing that reasoning under the above semantics is inherently intractable, even for very simple DLs. To the aim of overcoming such a high computational complexity of reasoning, we study sound approximations of the above semantics. Surprisingly, our computational analysis shows that reasoning under the approximated semantics is intractable even for tractable DLs. Finally, we identify suitable language restrictions of such DLs allowing for tractable reasoning under inconsistency-tolerant semantics.