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/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

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

OriginalspracheEnglisch
TitelProceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning
Redakteure/-innenMagdalena Ortiz, Renata Wassermann, Torsten Schaub
Herausgeber (Verlag)IJCAI Organization
Seiten366–375
Seitenumfang10
ISBN (elektronisch)978-1-956792-08-9
PublikationsstatusVeröffentlicht - Mai 2025
Peer-Review-StatusJa

Publikationsreihe

ReiheProceedings of the International Conference on Principles of Knowledge Representation and Reasoning
ISSN2334-1025

Externe IDs

Mendeley 8ae7bb56-2486-3c02-976e-d6e7b44e5be5
unpaywall 10.24963/kr.2025/36