Putting Perspective into OWL [sic]: Complexity-Neutral Standpoint Reasoning for Ontology Languages via Monodic S5 over Counting Two-Variable First-Order Logic
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
Standpoint extensions of KR formalisms have been recently introduced to incorporate multi-perspective modelling and reasoning capabilities. In such modal extensions, the integration of conceptual modelling and perspective annotations can be more or less tight, with monodic standpoint extensions striking a good balance as they enable advanced modelling while preserving good reasoning complexities. We consider the extension of C² – the counting two-variable fragment of first-order logic – by monodic standpoints. At the core of our treatise is a polytime translation of formulae in said formalism into standpoint-free C², requiring elaborate model-theoretic arguments. By virtue of this translation, the NEXPTIME-complete complexity of checking satisfiability in C² carries over to our formalism. As our formalism subsumes monodic S5 over C², our result also significantly advances the state of the art in research on first-order modal logics. As a practical consequence, the very expressive description logics ?ℋ?ℐ?ℬs and ?ℛ?ℐ?ℬs which subsume the popular W3C-standardized OWL 1 and OWL 2 ontology languages, are shown to allow for monodic standpoint extensions without any increase of standard reasoning complexity. We prove that NEXPTIME-hardness already occurs in much less expressive DLs as long as they feature both nominals and monodic standpoints. We also show that, with inverses, functionality, and nominals present, minimally lifting the monodicity restriction leads to undecidability.
Details
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning |
| Editors | Magdalena Ortiz, Renata Wassermann, Torsten Schaub |
| Publisher | IJCAI Organization |
| Pages | 366–375 |
| Number of pages | 10 |
| ISBN (electronic) | 978-1-956792-08-9 |
| Publication status | Published - May 2025 |
| Peer-reviewed | Yes |
Publication series
| Series | Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning |
|---|---|
| ISSN | 2334-1025 |
External IDs
| Mendeley | 8ae7bb56-2486-3c02-976e-d6e7b44e5be5 |
|---|---|
| unpaywall | 10.24963/kr.2025/36 |