Inproceedings3359: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Bartosz Bednarczyk (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Bartosz Bednarczyk (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 16: | Zeile 16: | ||
{{Publikation Details | {{Publikation Details | ||
|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 \in 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. | |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 \in 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. | ||
|Download= | |Download=Jelia2023-v2.pdf | ||
|Projekt=DeciGUT | |Projekt=DeciGUT | ||
|Forschungsgruppe=Computational Logic | |Forschungsgruppe=Computational Logic | ||
}} | }} | ||
Version vom 13. Juli 2023, 17:16 Uhr
Beyond ALCreg: Exploring Non-Regular Extensions of PDL with Description Logics Features
Bartosz BednarczykBartosz Bednarczyk
Bartosz Bednarczyk
Beyond ALCreg: Exploring Non-Regular Extensions of PDL with Description Logics Features
In Sarah Alice Gaggl, Maria Vanina Martinez, Magdalena Ortiz, eds., Proceedings of the 18th Edition of the European Conference on Logics in Artificial Intelligence (JELIA 2023), Lecture Notes in Computer Science, to appear. Springer International Publishing
Beyond ALCreg: Exploring Non-Regular Extensions of PDL with Description Logics Features
In Sarah Alice Gaggl, Maria Vanina Martinez, Magdalena Ortiz, eds., Proceedings of the 18th Edition of the European Conference on Logics in Artificial Intelligence (JELIA 2023), Lecture Notes in Computer Science, to appear. Springer International Publishing
- KurzfassungAbstract
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 \in 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. - Projekt:Project: DeciGUT
- Forschungsgruppe:Research Group: Computational LogicComputational Logic
@inproceedings{B2023,
author = {Bartosz Bednarczyk},
title = {Beyond {ALCreg:} Exploring Non-Regular Extensions of {PDL} with
Description Logics Features},
editor = {Sarah Alice Gaggl and Maria Vanina Martinez and Magdalena Ortiz},
booktitle = {Proceedings of the 18th Edition of the European Conference on
Logics in Artificial Intelligence (JELIA 2023)},
series = {Lecture Notes in Computer Science},
publisher = {Springer International Publishing},
year = {2023},
month = {September}
}
