Data Complexity in Expressive Description Logics With Path Expressions
This work addresses theoretical complexity issues in description logics, relevant for knowledge representation and reasoning, but is incremental as it completes known landscapes and reproves results.
The paper tackles the data complexity of satisfiability for the expressive description logic ZOIQ over quasi-forests, establishing NP-completeness, and uses the same technique to show coNEXPTIME-completeness for entailment of rooted queries in ZIQ.
We investigate the data complexity of the satisfiability problem for the very expressive description logic ZOIQ (a.k.a. ALCHb Self reg OIQ) 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.