代数模型计数
本文介绍了用于解决量化扩展逻辑编程中的第二级推理任务的算法框架 Second Level Algebraic Model Counting (2AMC),探讨了使用知识编译技术降低处理效率时的需要考虑变量阶数限制问题,进一步提出并实现了一种静态生成约束的策略,并在多个任务和基准测试上评估了有效性。
May, 2022
使用动态规划算法和代数决策图作为主要数据结构来计算布尔公式的精确文字加权模型计数,并将该方法实现在 ADDMC 中,通过在 1914 个标准模型计数基准测试中的比较,展示 ADDMC 在加权模型计数上显著优于现有最佳的求解器。
Jul, 2019
该论文研究的是加权一阶模型计数问题 (WFOMC),主要关注于能够在多项式时间内进行 WFOMC 的逻辑片段,其中包括经过拓展的两变量一阶逻辑碎片及其衍生的包含计数量词的逻辑碎片,通过在关系上添加定向无环图 (DAG) 公理,这篇论文对子领域进行了扩展。
Feb, 2023
本文提出了一种基于神经网络模型的加权 #DNF 模型计数方法,结合了近似模型计数和深度学习,可以在线性时间内准确估算模型数目,并在大规模 #DNF 实例中表现良好。
Apr, 2019
本文介绍了一种新的 lifted interpretations 工具,用于重构 Beame et al. 提出的多项式时间 FOMC 的闭合式公式,并将其扩展以涵盖基数约束、存在量词和计数量词(C2),同时仍然保持 domain-liftability。最后,我们展示了所获得的闭合形式促进了一种权重函数家族的自然定义,严格大于对称权重函数。
Oct, 2021
基于动态规划算法框架 ADD,我们提出了一种加权伪布尔计数工具 PBCounter 来对伪布尔公式进行加权模型计数,并且通过与基于 CNF 公式的模型计数工具进行实验比较,结果显示 PBCounter 在 CNF 公式上具有更好的性能。
Dec, 2023
本文提出了新的实现方案,利用命题知识编译来扩展推理,使用可处理布尔函数的可决策图作为基础模型计数和列举方案,在非线性势函数上处理非线性约束,并与最先进的 WMI 系统竞争。
Nov, 2018
本文研究了解析式权重一阶模型计数问题的 Lifted Inference 问题,通过提供一些结论,针对解析式的约束进行了分析讨论,并探讨了在对称概率性数据库中采用 Lifted Inference 的局限性和复杂性。
May, 2014
本文研究了在统计关系学中用于概率推断的加权一阶模型计数(WFOMC)任务,并证明了添加线性序公理后,WFOMC 仍可以在多项式时间内计算。作者提出了一种基于动态规划的新算法,可以在多项式时间内计算带有线性序的 WFOMC。
Nov, 2022