Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Description logics with pointwise circumscription
Institute of Logic and Computation, TU Wien, Austria.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-2344-9658
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0003-0632-0294
2023 (Engelska)Ingår i: Proceedings of the thirty-second international joint conference on artificial intelligence / [ed] Edith Elkind, International Joint Conferences on Artificial Intelligence , 2023, s. 3167-3175Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
International Joint Conferences on Artificial Intelligence , 2023. s. 3167-3175
Serie
International Joint Conference on Artificial Intelligence, ISSN 1045-0823
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:umu:diva-214549DOI: 10.24963/ijcai.2023/353Scopus ID: 2-s2.0-85170402945ISBN: 9781956792034 (digital)OAI: oai:DiVA.org:umu-214549DiVA, id: diva2:1800595
Konferens
32nd International Joint Conference on Artificial Intelligence, IJCAI 2023, Macao, August 19-25, 2023
Forskningsfinansiär
Wallenberg AI, Autonomous Systems and Software Program (WASP)Tillgänglig från: 2023-09-27 Skapad: 2023-09-27 Senast uppdaterad: 2023-11-24Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Ortiz, MagdalenaŠimkus, Mantas

Sök vidare i DiVA

Av författaren/redaktören
Ortiz, MagdalenaŠimkus, Mantas
Av organisationen
Institutionen för datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 17 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf