How I made my research more VISIBLE? Undecidability Results for ALC Extended with Visibly Pushdown Path Expressions.

Vortrag von Bartosz Bednarczyk

Veranstaltungsort: APB room 3027
Beginn: 13. Juli 2023 um 11:00
Ende: 13. Juli 2023 um 12:00
Event series: Research Seminar Logic and AI
iCal

Abstract: 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 ALCvpl, an extension of ALC with path expressions using visibly-pushdown languages, which was shown to be decidable by Löding et al. in 2007. We prove that decidability of ALCvpl is preserved when enriching the logic with functionality, but decidability is lost upon adding the seemingly innocent Self operator. We also consider the simplest non-regular (visibly-pushdown) language r#s# := {r^n s^n : n ∈ N}. We establish undecidability of the satisfiability problem for ALC extended with nominals and r#s#, as well as the query entailment problem, where such non-regular atoms are present in queries.

This work is based on the paper accepted to JELIA 2023, which is going to be submitted to Logical Methods in Computer Science next week.

The talk will take place in a hybrid fashion, physically in the APB room 3027, and online through the link:

https://bbb.tu-dresden.de/b/pio-zwt-smp-aus