On the Complexity of Dealing with Inconsistency in Description Logic Ontologies

Riccardo Rosati.
In Proceedings of the Twenty-second International Joint Conference on Artificial Intelligence (IJCAI 2011), pages 1057-1062, 2011.

 

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 CARsemantics, 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.

Bibtex entry:

@String{IJCAI-11 = "Proceedings of the Twenty-second International Joint Conference on Artificial Intelligence (IJCAI~2011)"}

@Inproceedings{Rosa11b,
author = "Riccardo Rosati",
title = "On the Complexity of Dealing with Inconsistency in Description Logic Ontologies",
booktitle = IJCAI-11,
pages = "1057--1062",
year = 2011,
}

Link to electronic version of published paper