Artale, Alessandro, Kontchakov, Roman, Mazzullo, Andrea and Wolter, Frank
(2024)
Non-Rigid Designators in Modal and Temporal Free Description Logics
(Extended Version).
[Preprint]
|
PDF
2405.07656v1.pdf - Other Download (544kB) | Preview |
Abstract
Definite descriptions, such as 'the General Chair of KR 2024', are a semantically transparent device for object identification in knowledge representation. In first-order modal logic, definite descriptions have been widely investigated for their non-rigidity, which allows them to designate different objects (or none at all) at different states. We propose expressive modal description logics with non-rigid definite descriptions and names, and investigate decidability and complexity of the satisfaction problem. We first systematically link satisfiability for the one-variable fragment of first-order modal logic with counting to our modal description logics. Then, we prove a promising NEXPTIME-completeness result for concept satisfiability for the fundamental epistemic multi-agent logic $\mathbf{S5}^{n}$ and its neighbours, and show that some expressive logics that are undecidable with constant domain become decidable (but Ackermann-hard) with expanding domains. Finally, we conduct a fine-grained analysis of decidability of temporal logics.
| Item Type: | Preprint |
|---|---|
| Uncontrolled Keywords: | cs.LO, cs.LO |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 03 Jul 2024 13:30 |
| Last Modified: | 17 Sep 2024 02:14 |
| DOI: | 10.48550/arxiv.2405.07656 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3182511 |
Altmetric
Altmetric
