技术摘要：在 $\mathcal{EL}^\bot$ 修补语义下结合属性进行 ABox 溯因

问题陈述

本文研究了描述逻辑（特别是 $\mathcal{EL}^\bot$）下基于**修补语义（repair semantics）**的 ABox 溯因问题。溯因旨在寻找一个假设（一组断言 $\mathcal{H}$），使得在将该假设添加到不一致的知识库 $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ 后，缺失的蕴含关系（观察结果）$\alpha$ 变为真。

在修补语义的背景下，不一致性通过考虑“修补”（ABox 的极大一致子集）来处理。本文重点研究了两种特定的语义：

1. 勇敢语义 (Brave Semantics)： 如果 $\alpha$ 在至少一个修补中成立，则认为 $\alpha$ 被蕴含。
2. AR (所有修补) 语义 (AR Semantics)： 如果 $\alpha$ 在所有修补中都成立，则认为 $\alpha$ 被蕴含。

虽然之前的研究 [17] 调查了针对单个理想属性（例如非平凡性、签名限制、冲突限制以及各种最小性标准）的溯因计算复杂度，但本文研究了这些属性的组合。核心研究问题是：要求一个假设同时满足多个属性（例如，既是非平凡的又是冲突限制的，或者既是子集最小的又是签名限制的）是否会导致其计算复杂度高于单独满足这些属性时的复杂度。

方法论

作者分析了针对属性组合的两种基本推理问题的计算复杂度：

1. 存在问题 (Existence Problem)： 是否存在满足给定属性的假设？
2. 验证问题 (Verification Problem)： 给定的 ABox $\mathcal{H}$ 是否满足这些属性并构成一个有效的假设？

该研究涵盖了以下属性的组合：

• 基本属性：
  • 非平凡性 (Non-triviality)： 假设不包含观察结果 $\alpha$。
  • 签名限制 ($\Sigma$-restricted)： 假设仅使用指定签名中的符号。
  • 冲突限制 (Conflict-confining)： 假设不会引入超出 $\mathcal{K}$ 中已存在的冲突之外的新冲突。
• 最小性标准：
  • 子集最小 ($\subseteq$-minimal)： 没有比当前假设更小的真假设（即不存在其真子集也是有效假设）。
  • 基数最小 ($\leq$-minimal)： 没有包含更少断言的假设是有效的。
  • 冲突最小 ($\subseteq_c$-minimal)： 没有引入更小冲突集的假设。

分析依赖于标准复杂度类（$\text{P}, \text{NP}, \text{coNP}, \text{DP}, \Sigma^P_2, \Pi^P_2$），并利用已知困难问题的归约（例如 QBF 有效性、蕴含/非蕴含组合）来建立下界，并使用带有预言机调用的猜想与检查算法来建立上界。

核心贡献与结果

1. 基本属性的组合（非最小性）

本文证明，结合基本属性通常不会增加复杂度，使其超过单个属性中最高的复杂度。

• $\Sigma$-限制 + 非平凡性： 对于勇敢语义，复杂度仍为 $\text{NP}$-完全；对于 AR 语义，为 $\Sigma^P_2$-完全。
• 冲突限制 + 非平凡性 / $\Sigma$-限制： 对于两种语义（Brave 和 AR），复杂度均增加至 $\Sigma^P_2$-完全。这是一个显著的结果，因为单独的冲突限制假设在勇敢语义下是 $\Sigma^P_2$-完全的，但在 AR 语义下仅为 $\text{coNP}$-完全；添加非平凡性或签名限制将 AR 的复杂度提升到了与勇敢语义一致的水平。

2. 与子集最小性 ($\subseteq$-minimality) 的组合

• 子集最小 + 非平凡 / $\Sigma$-限制： 其复杂度与验证单独的子集最小假设的复杂度一致（对于勇敢语义是 $\text{DP}$-完全，对于 AR 语义是 $\Pi^P_2$-完全）。
• 子集最小 + 冲突限制：
  • 对于 勇敢 (Brave) 语义：$\text{DP}$-完全。
  • 对于 AR 语义：复杂度在 $\Pi^P_2$ 中，且为 $\text{coNP}$-硬，但精确的上界目前仍是开放问题。

3. 与基数最小性 ($\leq$-minimality) 的组合

与子集最小性不同，基数最小性在与其他属性结合时往往会导致复杂度增加，这主要是因为非平凡性或签名限制通常不允许平凡假设（大小为 1）的存在。

• $\leq$-最小 + 非平凡 / $\Sigma$-限制： 复杂度在勇敢语义下增加到 $\text{DP}$-完全，在 AR 语义下增加到 $\Pi^P_2$-完全。
• $\leq$-最小 + 冲突限制：
  • 对于 勇敢 (Brave) 语义：$\Pi^P_2$-完全。
  • 对于 AR 语义：$\text{coNP}$-完全（由于引理 6，即对于 AR 语义，存在性意味着平凡假设是冲突限制的，因此复杂度保持不变，与单属性情况一致）。

4. 与冲突最小性 ($\subseteq_c$-minimality) 的组合

• $\subseteq_c$-最小 + 非平凡 / $\Sigma$-限制： 对于勇敢和 AR 语义，复杂度均为 $\Pi^P_2$-完全。
• 本文指出，将这些结果扩展到基数-冲突最小性 ($\leq_c$) 是困难的，因为较小的假设可能会触发指数级数量的新冲突，这暗示了潜在的 $\#\text{P}$-硬性。

重要性与主张

本文的主要观察是，要求假设具有额外的属性通常不会导致复杂度增加，只要这些属性不是涉及基数或冲突计数的最小性标准。

• 主要发现： 对于大多数基本属性（非平凡性、签名限制、冲突限制）和子集最小性的组合，其复杂度由涉及的单个属性中“最高”的复杂度决定。
• 例外： 涉及基数最小性或冲突最小性的组合经常导致更高的复杂度类（例如，从 $\text{coNP}$ 变为 $\Pi^P_2$ 或 $\text{DP}$）。
• 范围： 这些结果特定于 $\mathcal{EL}^\bot$ 下的勇敢语义和 AR 语义。作者指出，对于更具表达能力的逻辑（如 $\mathcal{ALC}$），复杂度很可能由蕴含问题本身（ExpTime）主导，使得这些特定的溯因区别影响较小。
• 未来工作： 作者指出了开放性的空白，特别是对于 $\subseteq$-最小冲突限制 AR 假设的精确复杂度，以及 $\text{DL-Lite}$ 中的复杂度图谱（在 $\text{DL-Lite}$ 中，他们怀疑由于结构特性，冲突限制可能会简化问题）以及在 IAR 语义下的情况。

文章总结道，虽然结合属性对于实际应用（例如，生成既是最小的又是冲突限制的解释）是理想的，但这并不一定意味着会以增加计算不可解性为代价。