Data Complexity in Expressive Description Logics with Path Expressions
Data Complexity in Expressive Description Logics with Path Expressions
Bartosz Bednarczyk
Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 3241-3249.
https://doi.org/10.24963/ijcai.2024/359
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.
Keywords:
Knowledge Representation and Reasoning: KRR: Description logics and ontologies
Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning