[DL] Description Logic Online Seminar March Edition

[Jean Christoph Jung]

Dear members of the DL community,

we are very happy to announce the next edition of the Description Logic Seminar for this Friday 8th of March at 2pm CET (https://dl.kr.org/seminar). This time, we have two speakers Sanja Lukumbuzya (TU Vienna) and Bartosz Bednarczyk (TU Dresden & University of Wroclaw), who will talk for 20+5 minutes each. Please find the respective abstracts below. 

Speaker 1:   Sanja Lukumbuzya
Title 1:          On the Complexity and Expressive Power of Ontology-Mediated Queries with Closed Predicates: Capturing coNP

Speaker 2:  Bartosz Bednarczyk
Title 2:         The Z family of Description Logics


The meeting will take place via Zoom:

https://tu-dortmund.zoom.us/j/96461411893?pwd=aGUrRkI4Y2VLSml3NlhVS0lvUU9sUT09
Meeting ID: 964 6141 1893
Passcode: 349261


Best wishes,
Ana, Magdalena, Meghyn, and Jean 


PS: Just a reminder that you can join the KR community Discord (and the #dl channel) via https://discord.gg/BBWpqEZT2v. Besides other relevant information regarding the KR & DL communities such as academic events and job offers, you will find talk announcements of the DL Seminar Series and other online events as well.

Abstracts
=======

In the recent years, there has been much interest in non-monotonic extensions of Description Logics (DLs). One prominent way of achieving non-monotonicity in DLs are closed predicate, i.e., ontological predicates that are to be interpreted under the closed-world assumption. In this talk, we will have a look into the data complexity and the expressive power of ontology-mediated query languages whose theory component is written in very expressive DLs that support closed predicates. Our DLs of choice also feature a tricky combination of inverses, nominals and number restrictions that additionally complicate things due to their lack of convenient model-theoretic properties. 
We will first see that answering atomic queries as well as a large class of “safe” first-order queries is coNP-complete in data complexity for ALCHOIF and ALCHOIQ with closed predicates, therefore showing that closed predicates do not make reasoning harder in these cases. Going a step further, we also explore the expressive power of OMQs with closed predicates from the descriptive complexity perspective, where the central question is to understand whether a given OMQ language is powerful enough to express all queries that can be computed within some bounds on time or space. 
To this end, we extend ALCHOIF with closed predicates with restricted forms of path expressions and nominal schemata without affecting the coNP upper bound in data complexity and we show that the obtained language coupled with instance queries is indeed powerful enough to express all coNP-computable Boolean queries.



In reasoning about graph-structured data, a significant role is played by description logics (DLs). Among many features present in extensions of the basic description logic ALC, an especially useful one is ·reg. It allows the user to navigate graph-structured data through regular path expressions, and is supported by the so-called Z-family of description logic. The Z family of DLs is among the most powerful knowledge representation formalisms on the verge of decidability. For its most expressive proponent, ZOIQ (a.k.a. ALCHbSelfregIOQ), featuring nominals (O), role inverses (I), and number restrictions (Q), querying is undecidable and even decidability of knowledge-base satisfiability is open, owing to the intricate interplay of the three mentioned features. Restricting the interaction of O, I, and Q however (or excluding one of the features altogether) leads to beneficial model-theoretic properties, which give rise to upper bounds of ExpTime for knowledge-base satisfiability and 2ExpTime for querying.
During the talk I will survey complexity-theoretic results on the Z family of DLs obtained by me and co-authors in the last 5 years of my PhD studies. I will also discuss open problems and explain how challenging they are to solve.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.zih.tu-dresden.de/pipermail/dl/attachments/20240305/0b6d66ff/attachment.htm>