研究描述逻辑中最小模型推理的不可判定性，揭示基础理论难题。
Minimal Model Reasoning in Description Logics: Don't Try This at Home!
- 通过最小化所有谓词扩展，分析描述逻辑中的最小模型推理机制。
- 发现即便在最简的EL语言中，概念可满足性也已不可判定。
- 提出环状条件约束以恢复可判定性，适合知识表示与逻辑推理研究者。
最小模型推理始终是知识表示的核心问题，但在描述逻辑（DLs）中仍缺乏充分理解。对某些谓词进行最小化、其余谓词自由或固定（如循环论域），虽已被探索但复杂度极高。而‘纯’最小模型——要求所有谓词的外延均最小——尚未被充分研究。本文针对主流描述逻辑，得到令人意外的负面结果：在$\ ext{EL}$语言中，最小模型下的概念可满足性即为不可判定。该不可判定性还扩展至一个极受限的元组生成依赖片段。为恢复可判定性，我们引入关于TBox的无环性条件，使最坏情况复杂度低于双指数时间，并建立与近期研究的逐点循环论域之间的联系；同时获得数据复杂性结果。最后简要考察DL-Lite家族，在已知DL-Lite$_{\text{core}}$有正结果的情况下，本文证明其扩展版DL-Lite$_{\text{horn}}$已达到ExpSpace-hard。
原文摘要 · Abstract (English)
Reasoning with minimal models has always been at the core of many knowledge representation techniques, but we still have only a limited understanding of this problem in Description Logics (DLs). Minimization of some selected predicates, letting the remaining predicates vary or be fixed, as proposed in circumscription, has been explored and exhibits high complexity. The case of `pure' minimal models, where the extension of all predicates must be minimal, has remained largely uncharted. We address this problem in popular DLs and obtain surprisingly negative results: concept satisfiability in minimal models is undecidable already for $\mathcal{EL}$. This undecidability also extends to a very restricted fragment of tuple-generating dependencies. To regain decidability, we impose acyclicity conditions on the TBox that bring the worst-case complexity below double exponential time and allow us to establish a connection with the recently studied pointwise circumscription; we also derive results in data complexity. We conclude with a brief excursion to the DL-Lite family, where a positive result was known for DL-Lite$_{\text{core}}$, but our investigation establishes ExpSpace-hardness already for its extension DL-Lite$_{\text{horn}}$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。