Data Complexity in Expressive Description Logics With Path Expressions

Talk by Bartosz Bednarczyk

Location: APB 3027
Start: 13. June 2024 at 11:00 am
End: 13. June 2024 at 12:00 pm
Research group: 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.