On the (un)decidability of fuzzy description logics under Łukasiewicz t-norm
On the (un)decidability of fuzzy description logics under Łukasiewicz t-norm
复制标题
Łukasiewicz t-范数下模糊描述逻辑的（不可）判定性
DOI：
10.1016/j.ins.2012.11.019
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
U. Straccia
中科院分区：
文献类型：
--
作者：
Marco Cerami;U. Straccia
最近有一些意想不到的结果，模糊描述逻辑（FDLs）与一般概念包含（GCI）。结果表明，与经典的情形不同，基于GCI的DL ALC不具有有限模型性质，所提出的推理算法既不正确也不完备，特别是知识库可满足性对于乘积逻辑是一个不可判定的问题.在这项工作中，我们表明，知识库的可满足性也是一个不可判定的问题，Eukasiewicz逻辑。我们还提供了一个决策算法的非循环ALC的知识库下通过一个混合线性规划（MILP）为基础的过程（注意，但是，这个问题的可判定性是已知的），通过Rukasiewicz逻辑。虽然类似的基于MILP的算法已经提出了在文献中的非循环ALC知识库下的Rukasiewicz逻辑，他们都没有表现出正式的证明其正确性和完整性，这是额外的贡献在这里。
Recently there have been some unexpected results concerning Fuzzy Description Logics (FDLs) with General Concept Inclusions (GCIs). They show that, unlike the classical case, the DL ALC with GCIs does not have the finite model property under Łukasiewicz Logic or Product Logic, the proposed reasoning algorithms are neither correct nor complete and, specifically, knowledge base satisfiability is an undecidable problem for Product Logic. In this work, we show that knowledge base satisfiability is also an undecidable problem for Łukasiewicz Logic. We additionally provide a decision algorithm for acyclic ALC knowledge bases under Łukasiewicz Logic via a Mixed Integer Linear Programming (MILP) based procedure (note, however, that the decidability of this problem is already known). While similar MILP based algorithms have been proposed in the literature for acyclic ALC knowledge bases under Łukasiewicz Logic, none of them exhibit formal proofs of their correctness and completeness, which is the additional contribution here.