On the Verge of Decidability: Querying Description Logics with Counting, Inverses and Nominals

Description Logics (DLs) are Knowledge Representation formalisms with a great significance for Semantic Web technologies. In this context, the most central reasoning task considered today is query answering over Description Logic knowledge bases under the finite model or arbitrary model semantics. Thereby, description logics that simultaneously encompass inverse roles, counting, and nominals are particularly challenging and the corresponding query entailment problem is usually on the verge of decidability. In the talk, we will review two results which demonstrate this.  For a slightly restricted class of conjunctive queries (i.e., queries with only simple roles), we show decidability of conjunctive query entailment in the popular description logics SHOIQ and SROIQ under the arbitrary model semantics. The proof is insofar peculiar as no complexity bounds can be derived from it. On the other hand, we will show undecidability of entailment of conjunctive queries for a fragment of SHOIQ under the finite model semantics. Finally we will discuss a few generic insights when dealing with these problems and talk about open cases.