Bartosz Bednarczyk - Exploring Non-Regular Extensions of Propositional Dynamic Logic with Description-Logics Features

lmcs:11618 - Logical Methods in Computer Science, May 14, 2024, Volume 20, Issue 2 - https://doi.org/10.46298/lmcs-20(2:7)2024
Exploring Non-Regular Extensions of Propositional Dynamic Logic with Description-Logics FeaturesArticle

Authors: Bartosz Bednarczyk

    We investigate the impact of non-regular path expressions on the decidability of satisfiability checking and querying in description logics extending ALC. Our primary objects of interest are ALCreg and ALCvpl, the extensions of with path expressions employing, respectively, regular and visibly-pushdown languages. The first one, ALCreg, is a notational variant of the well-known Propositional Dynamic Logic of Fischer and Ladner. The second one, ALCvpl, was introduced and investigated by Loding and Serre in 2007. The logic ALCvpl generalises many known decidable non-regular extensions of ALCreg. We provide a series of undecidability results. First, we show that decidability of the concept satisfiability problem for ALCvpl is lost upon adding the seemingly innocent Self operator. Second, we establish undecidability for the concept satisfiability problem for ALCvpl extended with nominals. Interestingly, our undecidability proof relies only on one single non-regular (visibly-pushdown) language, namely on r#s# := { r^n s^n | n in N } for fixed role names r and s. Finally, in contrast to the classical database setting, we establish undecidability of query entailment for queries involving non-regular atoms from r#s#, already in the case of ALC-TBoxes.


    Volume: Volume 20, Issue 2
    Published on: May 14, 2024
    Accepted on: April 9, 2024
    Submitted on: July 20, 2023
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Artificial Intelligence

    Consultation statistics

    This page has been seen 391 times.
    This article's PDF has been downloaded 196 times.