Data Complexity of Reasoning in Very Expressive Description Logics
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 466-470.
Abstract
Data complexity of reasoning in description logics (DLs) estimates the performance of reasoning algorithms measured in the size of the ABox only. We show that, even for the very expressive DL SHIQ, satisfiability checking is data complete for NP. For applications with large ABoxes, this can be a more accurate estimate than the usually considered combined complexity, which is EXPTIMEcomplete. Furthermore, we identify an expressive fragment, Horn-SHIQ, which is data complete for P, thus being very appealing for practical usage.
@inproceedings{ijcai2005p6,
title = {Data Complexity of Reasoning in Very Expressive Description Logics},
author = {Hustadt, Ullrich and Motik, Boris and Sattler, Ulrike},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {466--470},
year = {2005},
url = {https://ijcai.org/proceedings/2005/6},
}
TY - CPAPER TI - Data Complexity of Reasoning in Very Expressive Description Logics AU - Hustadt, Ullrich AU - Motik, Boris AU - Sattler, Ulrike T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 466 EP - 470 UR - https://ijcai.org/proceedings/2005/6 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
