Data Complexity in Expressive Description Logics With Path Expressions

From International Center for Computational Logic

Data Complexity in Expressive Description Logics With Path Expressions

Talk by Bartosz Bednarczyk
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.

https://bbb.tu-dresden.de/rooms/n5w-ghp-qoq-kts/join