AAAINov, 2014

稳定模型计数及其在概率逻辑编程中的应用

PDF
TL;DR本文研究了使用稳定模型语义进行推理的问题，提出了两种基于未建立的集合检测的实现技术，扩展了命题模型计数器到稳定模型计数器，可以在时间和空间使用方面显著优于现有的解决方案。
model countingprobabilistic logic programminginductive definitionsstable model semanticsunfounded set detection
发现论文，激发创造
  • 可扩展的近似模型计数器

    介绍了一种基于 SAT 求解器的算法和实现工具，用于处理大规模的 CNF 公式的近似计数问题。通过多项式调用的方式，能够高精度地估算满足条件的解数，同时针对过大的问题仍能提供高置信度的估算边界。

    Jun, 2013

  • SMT 中的近似计数和概率程序的值估计

    本篇论文介绍了一种从 SMT 到 #SMT 近似版本的约简方法，并提出了关于整数算术和线性实数算术的模型计数算法，通过对现代 SMT 求解器的高级启发式算法进行利用，运行时间为多项式级别并提供正式边界。我们使用这些算法来解决带有非确定性的无循环概率程序模型的值问题。

    Nov, 2014

  • 投影模型计数

    本文介绍了优先变量，非优先变量，以及计算仅涉及优先变量的模型计数问题，探讨了三种不同的计数方法，并在多组实验结果上进行了比较。

    Jul, 2015

  • 加权一阶模型计数的斯科莱曼化

    本研究提出了一种 Skolem 化算法来解决模型计数问题，扩展了一阶模型计数器的适用范围，使其能够用于概率逻辑程序等有向模型，同时还简化了抬升模型计数算法的设计。

    Dec, 2013

  • 正式验证的近似模型计数

    我们提出了第一个近似模型计数的认证框架，并且证明了其输出近似值的质量保证。

    Jun, 2024

  • 快速收敛的任意时间模型计数

    本篇论文设计了一种基于部分知识编译的新型近似模型计数方法 PartialKC，其在可伸缩性和准确性方面都表现显著优于以前的近似计数器，并可以收敛于精确计数器，实验证明其具有精确计数器可比的性能。

    Dec, 2022

  • 逻辑编程和稳定模型计算中的极值问题

    研究了逻辑程序中稳定模型的最大数量问题，得到了所有逻辑程序及分离逻辑程序的最大值，且提出了一种可在 O (3^{n/3}) 的最坏情况下找到 n 个子句程序的所有稳定模型的算法。

    Jan, 1999

  • 稳定模型与一种替代逻辑编程范式

    通过稳定模型语义重新审视逻辑编程在约束满足问题中的角色定义，提出一种函数符号被消除的新型逻辑编程系统，基于约束来描述问题的解决方案。该方法具有良好的应用范围、有力的计算算法和新型编程方法。

    Sep, 1998

  • 扩展和实现稳定模型语义

    提出了一种用于计算逻辑程序稳定模型语义的算法，强调使用有效的实现技术，特别地，提出了一种展望的实现和一种通过最小化搜索空间来产生良好的启发式方法。结果表明，稳定模型语义的逻辑程序具有更紧凑的逻辑程序表示，因此在某些问题上比命题逻辑优越。

    May, 2000

  • 构建精确的伪布尔模型计数器

    我们提出了第一个准确的伪布尔模型计数器 PBCount，它通过代数决策图的知识编译方法来实现。我们的实证评估表明，PBCount 可以计算 1513 个实例的计数，而当前最先进的方法只能处理 1013 个实例。我们的工作为进一步研究伪布尔公式的模型计数提供了几个方向，如预处理技术的开发和除知识编译之外的其他方法的探索。

    Dec, 2023