Data Complexity in Expressive Description Logics With Path Expressions

Vortrag von Bartosz Bednarczyk

Veranstaltungsort: APB 3027
Beginn: 13. Juni 2024 um 11:00
Ende: 13. Juni 2024 um 12:00
Forschungsgruppe: Computational Logic
Event series: Research Seminar Logic and AI
iCal

In my recent IJCAI paper I established NP-completeness of the satisfiability problem (w.r.t. the data complexity) of the maximal known decidable fragments ZIQ, ZOQ, and ZOI of the very description logic ZOIQ (a.k.a. ALCHb^self_regOIQ).

The proof uniformly deals with these three logics, by considering the DL ZOIQ but over forest-like structures dubbed quasi-forests.

During the talk, I will give a high-level overview of the proof, and discuss its main ingredients and challenges.