Data Complexity of Reasoning in Very Expressive Description Logics
Data Complexity of Reasoning in Very Expressive Description Logics
复制标题
极具表现力的描述逻辑中推理的数据复杂性
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
U. Sattler
中科院分区：
文献类型：
--
作者：
U. Hustadt;B. Motik;U. Sattler
描述逻辑推理的数据复杂度仅以ABox的大小来估计推理算法的性能。我们表明，即使是非常有表现力的DL SHIQ，可满足性检查是NP数据完整的。对于具有大的ABoxes的应用程序，这可能是比通常考虑的组合复杂度更准确的估计，组合复杂度是EXPTIME完全的。此外，我们确定了一个表达片段，角SHIQ，这是数据完整的P，因此是非常有吸引力的实际用途。
Data complexity of reasoning in description logics (DLs) estimates the performance of reasoning algorithms measured in the size of the ABox only. We show that, even for the very expressive DL SHIQ, satisfiability checking is data complete for NP. For applications with large ABoxes, this can be a more accurate estimate than the usually considered combined complexity, which is EXPTIME-complete. Furthermore, we identify an expressive fragment, Horn-SHIQ, which is data complete for P, thus being very appealing for practical usage.