Inproceedings3378

PublikationenPublications

• Nach AutorBy Author
  • Bartosz BednarczykBartosz Bednarczyk
• Nach ForschungsgruppeBy Research Group
  • Computational LogicComputational Logic

Toggle side column

Data Complexity in Expressive Description Logics With Path Expressions

Bartosz BednarczykBartosz Bednarczyk

• Download

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}
}