<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body style="overflow-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">Dear members of the KR community,<div><br></div><div>we are very happy to announce the next edition of the Description Logic Seminar for this Friday 8th of March at 2pm CET (<a href="https://dl.kr.org/seminar">https://dl.kr.org/seminar</a>). 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. <span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">Please find the respective abstracts below. </span></div><div><br></div><div>Speaker 1: <span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">Sanja Lukumbuzya</span></div><div>Title 1: <span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: "Helvetica Neue"; font-size: 13px;">On the Complexity and Expressive Power of Ontology-Mediated Queries with Closed Predicates: Capturing coNP</span></div><div><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: "Helvetica Neue"; font-size: 13px;"><br></span></div><div><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: "Helvetica Neue"; font-size: 13px;">Speaker 2: Bartosz Bednarczyk</span></div><div><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: "Helvetica Neue"; font-size: 13px;">Title 2: </span><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">The Z family of Description Logics</span></div><div><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br></span></div><div><br></div><div><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">The meeting will take place via Zoom:</span></div><div><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br></span></div><div><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><a href="https://tu-dortmund.zoom.us/j/96461411893?pwd=aGUrRkI4Y2VLSml3NlhVS0lvUU9sUT09">https://tu-dortmund.zoom.us/j/96461411893?pwd=aGUrRkI4Y2VLSml3NlhVS0lvUU9sUT09</a></span></div><div><div><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">Meeting ID: 964 6141 1893</span></div><div><font color="#000000">Passcode: 349261</font></div></div><div><font color="#000000"><br></font></div><div><font color="#000000"><br></font></div><div><font color="#000000">Best wishes,</font></div><div><font color="#000000">Ana, Magdalena, Meghyn, and Jean </font></div><div><font color="#000000"><br></font></div><div><font color="#000000"><br></font></div><div><font color="#000000">PS: Just a reminder that you can join the KR community Discord (and the #dl channel) via <a href="https://discord.gg/BBWpqEZT2v">https://discord.gg/BBWpqEZT2v</a>. 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.</font></div><div><font color="#000000"><br></font></div><div><font color="#000000">Abstracts</font></div><div><font color="#000000">=======</font></div><div><font color="#000000"><br></font></div><div><p style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); margin: 0px; font-stretch: normal; font-size: 13px; line-height: normal; font-family: "Helvetica Neue"; font-size-adjust: none; font-kerning: auto; font-variant-alternates: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-east-asian: normal; font-variant-position: normal; font-feature-settings: normal; font-optical-sizing: auto; font-variation-settings: normal;">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. </p><p style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); margin: 0px; font-stretch: normal; font-size: 13px; line-height: normal; font-family: "Helvetica Neue"; font-size-adjust: none; font-kerning: auto; font-variant-alternates: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-east-asian: normal; font-variant-position: normal; font-feature-settings: normal; font-optical-sizing: auto; font-variation-settings: normal;">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. </p><p style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); margin: 0px; font-stretch: normal; font-size: 13px; line-height: normal; font-family: "Helvetica Neue"; font-size-adjust: none; font-kerning: auto; font-variant-alternates: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-east-asian: normal; font-variant-position: normal; font-feature-settings: normal; font-optical-sizing: auto; font-variation-settings: normal;">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.</p></div><div><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br></span></div><div><br></div><div><br></div><div><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">In reasoning about graph-structured data, a significant role is played by description logics (DLs). </span><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">Among many features present in extensions of the basic description logic ALC, </span><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">an especially useful one is ·reg. It allows the user </span><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">to navigate graph-structured data through regular path expressions, and is supported by the so-called Z-family of description </span><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">logic. </span><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">The Z family of DLs is among the most powerful knowledge representation formalisms on the verge of decidability. </span><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">For its most expressive proponent, ZOIQ (a.k.a. ALCHbSelfregIOQ), featuring nominals (O), role inverses (I), and number restrictions (Q), querying is </span><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">undecidable and even decidability of knowledge-base satisfiability is open, owing to the intricate interplay </span><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">of the three mentioned features. Restricting the interaction of O, I, and Q however (or excluding one of </span><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">the features altogether) leads to beneficial model-theoretic properties, which give rise to upper bounds of </span><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">ExpTime for knowledge-base satisfiability and 2ExpTime for querying.</span><br style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">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. </span><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">I will also discuss open problems and explain how challenging they are to solve.</span></div></body></html>