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

Bartosz BednarczykBartosz Bednarczyk

Download

Bartosz Bednarczyk
Beyond ALCreg: Exploring Non-Regular Exten- sions 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

Details
Bibtex

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 Exten- sions 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}
}