Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Description logics with pointwise circumscription
Institute of Logic and Computation, TU Wien, Austria.
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0002-2344-9658
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0003-0632-0294
2023 (English)In: Proceedings of the thirty-second international joint conference on artificial intelligence / [ed] Edith Elkind, International Joint Conferences on Artificial Intelligence , 2023, p. 3167-3175Conference paper, Published paper (Refereed)
Abstract [en]

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 EXPTIMEcomplete, 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.

Place, publisher, year, edition, pages
International Joint Conferences on Artificial Intelligence , 2023. p. 3167-3175
Series
International Joint Conference on Artificial Intelligence, ISSN 1045-0823
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-214549DOI: 10.24963/ijcai.2023/353Scopus ID: 2-s2.0-85170402945ISBN: 9781956792034 (electronic)OAI: oai:DiVA.org:umu-214549DiVA, id: diva2:1800595
Conference
32nd International Joint Conference on Artificial Intelligence, IJCAI 2023, Macao, August 19-25, 2023
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)Available from: 2023-09-27 Created: 2023-09-27 Last updated: 2023-11-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Ortiz, MagdalenaŠimkus, Mantas

Search in DiVA

By author/editor
Ortiz, MagdalenaŠimkus, Mantas
By organisation
Department of Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 112 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf