Data Complexity in Expressive Description Logics With Path Expressions

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Data Complexity in Expressive Description Logics With Path Expressions

Vortrag von 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