Daily Arxiv

전 세계에서 발간되는 인공지능 관련 논문을 정리하는 페이지 입니다.
본 페이지는 Google Gemini를 활용해 요약 정리하며, 비영리로 운영 됩니다.
논문에 대한 저작권은 저자 및 해당 기관에 있으며, 공유 시 출처만 명기하면 됩니다.

Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics

Created by
  • Haebom
Category
Empty

저자

Meghyn Bienvenu, Quentin Maniere

개요

본 논문은 최근 도입된 비용 기반 의미론 하에서 불일치 가중치 설명 논리(DL) 지식 기반 질의에 대한 데이터 복잡성을 연구한다. 위반된 공리 및 단언의 가중치에 따라 각 해석에 비용을 할당하고, 최적 또는 제한된 비용을 갖는 모든(또는 일부) 해석을 고려하여 확실 및 가능 질의 응답을 결정한다. $\mathcal{EL}\bot$에서 $\mathcal{ALCO}$ 사이의 DL에 초점을 맞춘 초기 연구와 달리, 본 논문은 역 역할 및 역할 포함을 포함할 수 있는 DL을 고려하여 주요 DL-Lite 방언을 다룬다. 본 연구는 여러 하한선을 강화하고 최적 비용 확실 응답 의미론의 정확한 복잡성을 명시함으로써 기존 결과를 크게 넘어선다. 또한, 모든 기존 연구가 비용 기반 의미론의 난해함을 보여주는 반면, $\text{DL-Lite}^\mathcal{H}\mathsf{bool}$ 온톨로지와 고정된 비용 제한을 고려할 경우, 인스턴스 질의에 대한 확실 응답과 결합 질의에 대한 가능 응답은 1차 논리 재작성을 사용하여 계산될 수 있으며, 따라서 가장 낮은 데이터 복잡성($\mathsf{TC}_0$)을 갖는다는 놀라운 결과를 제시한다.

시사점, 한계점

시사점:
비용 기반 의미론에서 불일치 DL 질의의 데이터 복잡성에 대한 새로운 하한 및 상한을 제시.
$\text{DL-Lite}^\mathcal{H}_\mathsf{bool}$ 온톨로지와 고정 비용 제한 하에서 특정 질의 유형에 대해 매우 낮은 데이터 복잡성($\mathsf{TC}_0$)을 달성함을 보임.
기존 연구의 범위를 확장하여 역 역할 및 역할 포함을 포함하는 DL을 고려.
한계점:
특정 질의 유형과 특정 DL-Lite 하위 집합에 초점을 맞춤.
비용 기반 의미론의 일반적인 활용 가능성에 대한 추가 연구 필요.
최적 비용 확실 응답 의미론에 대한 상한은 여전히 존재하지 않음.
👍