Putting Perspective into OWL [sic]: Complexity-Neutral Standpoint Reasoning for Ontology Languages via Monodic S5 over Counting Two-Variable First-Order Logic
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
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
| Originalsprache | Englisch |
|---|---|
| Titel | Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning |
| Redakteure/-innen | Magdalena Ortiz, Renata Wassermann, Torsten Schaub |
| Herausgeber (Verlag) | IJCAI Organization |
| Seiten | 366–375 |
| Seitenumfang | 10 |
| ISBN (elektronisch) | 978-1-956792-08-9 |
| Publikationsstatus | Veröffentlicht - Mai 2025 |
| Peer-Review-Status | Ja |
Publikationsreihe
| Reihe | Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning |
|---|---|
| ISSN | 2334-1025 |
Externe IDs
| Mendeley | 8ae7bb56-2486-3c02-976e-d6e7b44e5be5 |
|---|---|
| unpaywall | 10.24963/kr.2025/36 |