为什么在OWL EL中添加析取会使计算更复杂？

Question

我试图理解为什么向OWL EL添加析取会使语言在计算上更复杂(例如,为什么在多项式时间内添加'或'会使可满足性,一致性和/或包含检查变得不可能......他们是p-标准OWL EL中的时间)

除其他外,OWL EL概况不允许分离和否定.我无法理解为什么使用现有的OWL EL结构无法实现析取,通过创建包含给定类表达式的析取子集作为子集的新类.

例如,可以表达式(在曼彻斯特语法中):

  Class1 and (Class2 or Class3) and (Property1 some (Class3 or Class4))

被改写为:

  Class1 and NewClass1 and (Property1 some NewClass2)

  where Class2 is a subset of NewClass1,
        Class3 is a subset of NewClass1,
        Class3 is a subset of NewClass2,
        Class4 is a subset of NewClass2

？

我知道答案是'不',但为什么'不'？

Answer 1

通过"重写",我猜你的意思是你用C or D命名的类替换原始本体中的所有析取表达式C_or_D并添加公理:

`C subClassOf C_or_D`
`D subClassOf C_or_D`

你必须递归地这样做,因为C(分别D)可能本身包含析取.然后你有一个本体论,有更多的公理,更多的概念名称,但有一个看似非常接近的语义.但是,正如你怀疑自己,你错了.请考虑以下示例:

A subClass C or D
C subClassOf B
D subClassOf B

使用您提议的重写,您将获得:

A subClass C_or_D
C subClassOf C_or_D
D subClassOf C_or_D
C subClassOf B
D subClassOf B

第一个本体论需要A subClassOf B,而第二个本体论不需要.

一般来说,分离在推理中是有问题的,因为它导致了替代方案.如果你想要检查一致性,你必须尝试为替代的一个分支找到世界的可能安排,如果失败,找到替代的第二个分支的世界的可能安排.每个析取可能会使处理时间乘以2.对于n个析取,你可能得到2 个探索的可能性.

在命题逻辑中也是如此:如果你有一个不会出现分离的联合正规形式,那么可满足性就是一个愚蠢的简单问题.当你允许分离时,它是NP完全的.