Data Complexity in Expressive Description Logics With Path Expressions

Bartosz BednarczykBartosz Bednarczyk

Bartosz Bednarczyk
Data Complexity in Expressive Description Logics With Path Expressions
Proceedings of the 33rd International Joint Conference on Artificial Intelligence, IJCAI 2024, to appear. ijcai.org

Details
Bibtex

KurzfassungAbstract
We investigate the data complexity of the satisfiability problem for the very expressive description logic ZOIQ (a.k.a. ALCHb^self_regOIQ) 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.
Projekt:Project: DeciGUT
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{B2024,
  author    = {Bartosz Bednarczyk},
  title     = {Data Complexity in Expressive Description Logics With Path
               Expressions},
  booktitle = {Proceedings of the 33rd International Joint Conference on
               Artificial Intelligence, {IJCAI} 2024},
  publisher = {ijcai.org},
  year      = {2024},
  month     = {August}
}