Given a knowledge base and an observation as a set of facts, ABox abduction aims at computing a hypothesis that, when added to the knowledge base, is sufficient to entail the observation. In signature-based ABox abduction, the hypothesis is further required to use only names from a given set. This form of abduction has applications such as diagnosis, KB repair, or explaining missing entailments. It is possible that hypotheses for a given observation only exist if we admit the use of fresh individuals and/or complex concepts built from the given signature, something most approaches for ABox abduction so far do not support or only support with restrictions. In this paper, we investigate the computational complexity of this form of abduction -- allowing either fresh individuals, complex concepts, or both -- for various description logics, and give size bounds on the hypotheses if they exist.
翻译：根据知识基础和作为一组事实的观察,ABox绑架的目的是计算一种假设,即如果添加到知识库中,就足以引起观察。在基于签名的ABox绑架中,进一步要求假设只使用某一组人的名字。这种形式的绑架有诊断、KB修理或解释缺失的必然后果等应用。只有当我们承认使用从特定签字中建立的新个人和/或复杂概念,而迄今为止对ABox绑架采取的大多数方法都并不支持或仅仅支持限制措施,就有可能存在特定观察的假设。在本文中,我们调查了这种形式的绑架的计算复杂性 -- -- 允许新的个人、复杂的概念或两者兼有 -- -- 用于各种描述逻辑,并在存在假说的情况下对假说进行尺寸限制。
相关内容
微信扫码咨询专知VIP会员