Di Stefano, F., Ortiz, M., & Šimkus, M. (2023). Description Logics with Pointwise Circumscription. In E. Elking (Ed.), Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23) (pp. 3167–3175). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2023/353
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
Erschienen in:
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)
-
ISBN:
978-1-956792-03-4
-
Datum (veröffentlicht):
2023
-
Veranstaltungsname:
Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)
en
Veranstaltungszeitraum:
19-Aug-2023 - 25-Aug-2023
-
Veranstaltungsort:
China
-
Umfang:
9
-
Verlag:
International Joint Conferences on Artificial Intelligence
-
Peer Reviewed:
Ja
-
Keywords:
Description Logics; Non-monotonic Reasoning; Ontologies; Knowledge Representation and Reasoning
en
Abstract:
Circumscription is one of the most powerful ways to extend Description Logics (DLs) with non-monotonic reasoning features, albeit with huge computational costs and undecidability in many cases. In this paper, we introduce pointwise circumscription for DLs, which is not only intuitive in terms of knowledge representation, but also provides a sound approximation of classic circumscription and has reduced computational complexity. Our main idea is to replace the second-order quantification step of classic circumscription with a series of (pointwise) local checks on all domain elements and their immediate neighbourhood. Our main positive results are for ontologies in DLs ALCIO and ALCI: we prove that for TBoxes of modal depth 1 (i.e. without nesting of existential or universal quantifiers) standard reasoning problems under pointwise circumscription are (co)NExpTime-complete and ExpTime-complete, respectively. The restriction of modal depth still yields a large class of ontologies useful in practice, and it is further justified by a strong undecidability result for pointwise circumscription with general TBoxes in ALCIO.
en
Projekttitel:
Compiling Knowledge into Applications: P30873-N35 (FWF - Österr. Wissenschaftsfonds) Ontology-mediated Queries for Graph Databases: P 30360-N35 (FWF - Österr. Wissenschaftsfonds)
-
Projekt (extern):
Knut and Alice Wallenberg Foundation Austrian Science Fund (FWF)
-
Projektnummer:
Wallenberg AI, Autonomous Systems and Software Program (WASP) W1255