IJCAI 2024poster1 citations
Data Complexity in Expressive Description Logics with Path Expressions
Abstract
We investigate the data complexity of the satisfiability problem for the very expressive description logic ZOIQ (a.k.a. ALCHbSelfregOIQ) over quasi-forests and establish its NP-completeness. This completes the data complexity landscape for decidable fragments of ZOIQ, and reproves known results on decidable fragments of OWL2 (SR family). Using the same technique, we establish coNEXPTIME-completeness (w.r.t. the combined complexity) of the entailment problem of rooted queries in ZIQ.
Knowledge Representation and Reasoning: KRR: Description logics and ontologiesKnowledge Representation and Reasoning: KRR: Computational complexity of reasoning
BibTeX
@inproceedings{ijcai2024p359,
title = {Data Complexity in Expressive Description Logics with Path Expressions},
author = {Bednarczyk, Bartosz},
booktitle = {Proceedings of the Thirty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-24}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Kate Larson},
pages = {3241--3249},
year = {2024},
month = {8},
note = {Main Track},
doi = {10.24963/ijcai.2024/359},
url = {https://doi.org/10.24963/ijcai.2024/359},
}