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 방언을 다룹니다. 또한, 최적 비용 확실 답변 의미론의 정확한 복잡성을 파악하고, DL-Lite$^\mathcal{H}\mathsf{bool}$ 온톨로지와 고정 비용 경계를 고려할 경우, 인스턴스 쿼리의 확실 답변 및 결합 쿼리의 가능한 답변을 1차 논리 재작성을 통해 계산할 수 있음을 밝혀 가장 낮은 데이터 복잡성($\mathsf{TC}_0$)을 가짐을 보였습니다.

시사점, 한계점

시사점:
최적 비용 확실 답변 의미론의 정확한 복잡성을 파악했습니다.
DL-Lite$^\mathcal{H}_\mathsf{bool}$ 온톨로지와 고정 비용 경계 조건 하에서 인스턴스 쿼리의 확실 답변 및 결합 쿼리의 가능한 답변이 $\mathsf{TC}_0$ 복잡성을 가짐을 밝혔습니다.
기존 연구의 데이터 복잡성 분석을 개선했습니다.
한계점:
논문에 구체적인 한계점 언급 없음. (논문 내용을 요약한 것이므로, 논문 자체의 한계점에 대한 직접적인 언급은 포함되지 않음)
👍