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

{{Veranstaltung
|Titel EN=How I made my research more VISIBLE? Undecidability Results for ALC Extended with Visibly Pushdown Path Expressions.
|Beschreibung EN=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 was recently accepted to JELIA 2023 and 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
|Veranstaltungsart=Vortrag
|Start=2023/07/13 11:00:00
|Ende=2023/07/13 12:00:00
|Raum=APB room 3027
|Vortragender=Bartosz Bednarczyk
|Event series=Research Seminar Logic and AI
|In News anzeigen=1
}}