The Complexity of Lattice-Based Fuzzy Description Logics
The Complexity of Lattice-Based Fuzzy Description Logics
复制标题
基于格的模糊描述逻辑的复杂性
DOI：
10.1007/s13740-012-0013-x
复制
发表时间：
2013
影响因子：
--
通讯作者：
R. Peñaloza
中科院分区：
文献类型：
--
作者：
Stefan Borgwardt;R. Peñaloza
研究了基于有限剩余格的语义模糊描述逻辑的推理复杂性。对于逻辑$$\数学运算$$，我们证明了判定概念的可满足性和包含，无论有没有Tbox，都是ExpTime-Complete问题。在$$\Mathcal{Alchi}$$及其变体$$\Mathcal{SI}$$中，当限制到非循环Tbox时，这些决策问题成为PSpace-Complete。这与在$$\mathcal{alc}$$和$$\mathcal shi$$之间的清晰描述逻辑中推理的已知复杂性界限相匹配。
We study the complexity of reasoning in fuzzy description logics with semantics based on finite residuated lattices. For the logic $$\mathcal SHI $$, we show that deciding satisfiability and subsumption of concepts, with or without a TBox, are ExpTime-complete problems. In $$\mathcal{ALCHI }$$ and a variant of $$\mathcal{SI }$$, these decision problems become PSpace-complete when restricted to acyclic TBoxes. This matches the known complexity bounds for reasoning in crisp description logics between $$\mathcal{ALC }$$ and $$\mathcal SHI $$.