用模拟关系求解EL/ELI逻辑的本体拟合问题，提升查询匹配效率。
Fitting Horn DL Ontologies to ABox and Query Examples: A Tale of Simulation Quantifiers and Finite Models
- 基于模拟关系构建本体拟合判定方法，解决正负例匹配难题。
- 原子查询在EL/ELI下为多项式时间可解，合取查询达Σ₂ᴾ复杂度。
- 适用于知识图谱对齐与轻量级本体学习场景，适合推理效率优先的用户。
我们研究将描述逻辑（DL）本体拟合到给定的正负例（即一个ABox和布尔查询）的问题。尽管先前工作已探讨过表达力强的DL如ALC和ALCI，本文聚焦于霍恩型的EL和ELI及其带底概念的扩展。查询语言包括原子查询（AQs）、合取查询（CQs）以及它们的并集（UCQs）。我们通过模拟关系刻画了拟合本体的存在性，据此开发决策算法，并明确了精确计算复杂度：对于原子查询，EL和ELI均为PTime可解；对于合取查询和并查询，分别为Σ₂ᴾ-完全（EL）和ExpTime-完全（ELI）。加入底概念不改变任何复杂度。有趣的是，从ALC/ALCI转向EL/ELI并未简化问题，反而引入了额外的技术挑战。
原文摘要 · Abstract (English)
We study the problem of fitting a description logic (DL) ontology to a given set of positive and negative examples that take the form of an ABox and a Boolean query. While previous work has investigated this problem for the expressive DLs ALC and ALCI, we here focus on the Horn DLs EL and ELI, as well as their extensions with the bottom concept. As the query language, we consider atomic queries (AQs), conjunctive queries (CQs), and unions thereof (UCQs). We provide characterization of the existence of a fitting ontology based on simulations, use them to develop decision procedures, and clarify the exact computational complexity. For AQs, the problem is in PTime for both EL and ELI. For CQs and UCQs, it is $Σ_2^P$-complete for EL and ExpTime-complete for ELI. Adding the bottom concept does not change any of these complexities. Interestingly, moving from ALC and ALCI to EL and ELI introduces additional technical challenges rather than simplifying the matter.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。