arXiv:2308.11738v4 声明类型: 替换 摘要: 加权一阶模型计数 (WFOMC) 是统计关系学习模型中概率推理的基础。由于 WFOMC 在一般情况下是不可计算的（$\#$P完全），因此可以实现多项式时间 WFOMC 的逻辑片段非常重要。这样的片段被称为领域提升的。最近的研究表明，扩展了计数量化器的嵌套一阶逻辑的二变量片段（$\mathrm{C^2}$）是领域提升的。然而，许多现实世界的属性，如引用网络中的无环性和社交网络中的连通性，无法在 $\mathrm{C^2}$ 中或一般的一阶逻辑中建模。在本文中，我们扩展了 $\mathrm{C^2}$ 的领域提升性，引入了多个这样的属性。我们证明，在 $\mathrm{C^2}$ 语句中的一个关系被限制为表示有向无环图、连通图、树（相应地，有向树）或森林（相应地，有向森林）时，$\mathrm{C^2}$ 语句仍是领域提升的。我们所有结果都基于一种新颖且通用的“通过分裂计数”的方法。除了在概率推理中的应用外，我们的结果提供了一种计数组合结构的一般框架。我们在离散数学文献中扩展了关于有向无环图、系统发生学网络等方面的许多先前结果。