说明:我们观察到W *层次结构是更广为人知的W层次结构的一种变体(由Downey,Fellows和Taylor [7]引入),与W层次结构重合,尽管不是层级明智的,但它是整个层次结构。 更确切地说,我们证明对于每个t> 2,W [2t-2]的W * [t]子集的W [t]子集。之前知道W [1] = W * [1]和W [2 ]-W * [2]。 我们的第二个主要结果是根据“ Fagin可定义的问题”对W *层次结构进行了新的逻辑表征。 作为副产品,我们还在模型检查问题方面获得了对先前层次结构特
<weixin_38620314> 上传 | 大小:216kb