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

Bartosz BednarczykBartosz Bednarczyk

ISBN: 978-3-031-43619-2
Download
DOI Link

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), Logics in Artificial Intelligence, 289--305, 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. The paper present a series of undecidability results. We prove undecidability of ALCvpl with the seemingly innocent Self operator. Then, 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.
Weitere Informationen unter:Further Information: Link
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    = {Logics in Artificial Intelligence},
  publisher = {Springer International Publishing},
  year      = {2023},
  month     = {September},
  pages     = {289--305},
  doi       = {10.1007/978-3-031-43619-2_21}
}