Beyond ALCreg: Exploring Non-Regular Extensions of PDL with Description Logics Features

We investigate the impact of non-regular path expressions on the decidability of satisfiability checking and querying in description logics. Our primary object of interest is ALC(vpl), an extension of ALC with path expressions using visibly-pushdown languages, which was shown to be decidable by Loding et al. in 2007. The paper present a series of undecidability results. We prove undecidability of ALC(vpl) with the seemingly innocent Self operator. Then, we consider the simplest non-regular (visibly-pushdown) language r(#)s(#) := {r(n)s(n) | n is an element of N}. We establish undecidability of the concept satisfiability problem for ALCreg extended with nominals and r(#) s(#), as well as of the query entailment problem for ALC-TBoxes, where such non-regular atoms are present in queries.