{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:22Z","timestamp":1753894402320,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We investigate the impact of non-regular path expressions on the decidability\nof satisfiability checking and querying in description logics extending ALC.\nOur primary objects of interest are ALCreg and ALCvpl, the extensions of with\npath expressions employing, respectively, regular and visibly-pushdown\nlanguages. The first one, ALCreg, is a notational variant of the well-known\nPropositional Dynamic Logic of Fischer and Ladner. The second one, ALCvpl, was\nintroduced and investigated by Loding and Serre in 2007. The logic ALCvpl\ngeneralises many known decidable non-regular extensions of ALCreg.\n  We provide a series of undecidability results. First, we show that\ndecidability of the concept satisfiability problem for ALCvpl is lost upon\nadding the seemingly innocent Self operator. Second, we establish\nundecidability for the concept satisfiability problem for ALCvpl extended with\nnominals. Interestingly, our undecidability proof relies only on one single\nnon-regular (visibly-pushdown) language, namely on r#s# := { r^n s^n | n in N }\nfor fixed role names r and s. Finally, in contrast to the classical database\nsetting, we establish undecidability of query entailment for queries involving\nnon-regular atoms from r#s#, already in the case of ALC-TBoxes.<\/jats:p>","DOI":"10.46298\/lmcs-20(2:7)2024","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:15:13Z","timestamp":1715674513000},"source":"Crossref","is-referenced-by-count":0,"title":["Exploring Non-Regular Extensions of Propositional Dynamic Logic with Description-Logics Features"],"prefix":"10.46298","volume":"Volume 20, Issue 2","author":[{"given":"Bartosz","family":"Bednarczyk","sequence":"first","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2024,5,14]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/13581\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/13581\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:15:14Z","timestamp":1715674514000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/11618"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,14]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(2:7)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2307.09913v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2307.09913v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2307.09913v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2307.09913","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2307.09913","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2024,5,14]]},"article-number":"11618"}}