Jul, 2024

权重一阶模型计数与图多项式的连接

HTML
PDF
TL;DR给定一个一阶逻辑句子和一个域，加权一阶模型计数问题通过计算给定逻辑句子的模型在给定域上的加权和来解决该问题。通过关联加权一阶模型计数问题与图多项式，我们定义了一阶逻辑句子的弱连通性多项式和强连通性多项式。这些多项式具有一些有趣的性质，可以在多项式时间内计算，可以用于解决已知可计算的公理以及新的公理，同时可以计算一些重要的图多项式。
发现论文，激发创造
  • 理解提升推理和非对称加权模型计数的复杂性

    本文研究了解析式权重一阶模型计数问题的Lifted Inference问题，通过提供一些结论，针对解析式的约束进行了分析讨论，并探讨了在对称概率性数据库中采用Lifted Inference的局限性和复杂性。

    May, 2014

  • 对称加权一阶模型计数

    在本文中，我们研究了对称加权有限模型计数问题的复杂性，旨在解决知识库推理中的软约束问题。我们证明了特定情况下该问题的数据复杂度可在多项式时间内计算，但在一般情况下该问题在#P中是完全的复杂度。

    Dec, 2014

  • 带计数量词的二元分片的加权一阶模型计数

    该研究将Van den Broeck等人关于加权第一阶模型计数在一阶逻辑中的多项式解法扩展到同时带有计数量词的两变量片段，探究其时间复杂度。

    Jul, 2020

  • 带基数约束和计数量词的FO2加权模型计数：一个封闭式公式

    本文介绍了一种新的 lifted interpretations 工具，用于重构 Beame et al. 提出的多项式时间 FOMC 的闭合式公式，并将其扩展以涵盖基数约束、存在量词和计数量词（C2），同时仍然保持 domain-liftability。最后，我们展示了所获得的闭合形式促进了一种权重函数家族的自然定义，严格大于对称权重函数。

    Oct, 2021

  • 线性序公理的提升推理

    本文研究了在统计关系学中用于概率推断的加权一阶模型计数（WFOMC）任务，并证明了添加线性序公理后，WFOMC仍可以在多项式时间内计算。作者提出了一种基于动态规划的新算法，可以在多项式时间内计算带有线性序的WFOMC。

    Nov, 2022

  • 带有有向无环图公理的加权一阶模型计数

    该论文研究的是加权一阶模型计数问题(WFOMC)，主要关注于能够在多项式时间内进行WFOMC的逻辑片段，其中包括经过拓展的两变量一阶逻辑碎片及其衍生的包含计数量词的逻辑碎片，通过在关系上添加定向无环图(DAG)公理，这篇论文对子领域进行了扩展。

    Feb, 2023

  • 一阶模型计数的递归函数合成：挑战、进展和猜想

    本文介绍了一种新的基于图的算法，用于解决一类叫做一阶模型计数的计算问题，相比之前算法，新算法能够解决更多复杂的递归运算并提高计算效率。

    Jun, 2023

  • 对称加权一阶模型采样的提升算法

    证明了一种高效的采样算法，解决了带有计数量词的一阶逻辑的两个变量片段的权重模型采样在多项式时间内可行的问题。

    Aug, 2023

  • 超越一阶逻辑的提升推理

    据我们展开的C²的领域扩展，任何C²句子在其关系受限于表示有向无环图、连通图、树（或有向树）、森林（或有向森林）时仍保持领域可提升，这提供了一个计算组合结构的通用框架。

    Aug, 2023

  • PBCounter: 伪布尔公式上的加权模型计数

    基于动态规划算法框架ADD，我们提出了一种加权伪布尔计数工具PBCounter来对伪布尔公式进行加权模型计数，并且通过与基于CNF公式的模型计数工具进行实验比较，结果显示PBCounter在CNF公式上具有更好的性能。

    Dec, 2023