关于有界树宽的 CNFs 的 OBDDs
本文旨在确定哪些布尔函数可以由小型的 SDDs 表示,同时将多项式大小的布尔函数表示集合与来自 Darwiche 和 Marquis 经典知识编译地图的表示类型进行比较。最主要的结果是通过等效的不明确的非确定性 OBDDs 对 SDDs 进行准多项式仿真,回答了 SDDs 和超过 OBDDs 的 FBDDs 相对简洁性之间的一个开放问题。
Feb, 2018
本文介绍了一种名为 sentential decision diagrams (SDDs) 的表达语言,证明了在布尔函数的表示中 SDDs 比 ordered binary decision diagrams (OBDDs) 更简洁,该结论解决了知识编译中的一个开放性问题,并且在人工智能和知识编译等领域有广泛的应用。
Jan, 2016
本文研究了如何将一个二进制神经网络的决策函数编译成可行的表示形式,如有序二进制决策图和命题决策图,并讨论了使用这些表示形式来验证神经网络的鲁棒性和计算期望鲁棒性的方法。此外,本文还提出了一种基于伪多项式时间算法编译单个神经元的高效方法,并在手写数字数据集中展示了两个神经网络的高准确度但鲁棒性不同的案例研究。最后,实验证明使用命题决策图可以获得神经网络的紧凑表示形式。
Apr, 2020
论文提出了关于大规模自然问题中精确概率推断效率的新极限,尤其是给出了关于知识编译到 SDD 和 DNNF 形式的新下限,并利用 SDD 大小与最佳划分通信复杂度的关系证明了一类大型问题的 SDD 大小的指数下限。
Jun, 2015
本文介绍了可分解否定范式(DNNF)作为可行的命题理论形式,并提供了一些在多项式时间内可以执行的强大逻辑操作。在此基础上,本文提出了将任何合取范式(CNF)转化为 DNNF 的算法,并提供其空间和时间复杂度上的结构保证。同时它也介绍了将有序二叉决策图(OBDD)表示的命题理论转换为等价的 DNNF 的线性时间算法。接着,介绍了采用新的操作在 d-DNNF 上遍历之后实现线性时间、完整的信念修正系统。
Mar, 2000
通过证明经过单次读取分支程序(nrobp)的空间下限为 n^Ω(k),针对原始图的树宽不超过 k 的 cnfs 可证明 nrobp 的固定参数空间复杂性不可行,在此基础上我们得到自由二元决策图和决策可分解否定正常形式之间的近多项式分离。
Nov, 2014
本文采用量化布尔公式减少作为一种新的方法来展示固定参数线性算法,研究人工智能领域的几个已知问题,其中大部分问题已经通过使用 Courcelle 定理或动态规划证明了其固定参数线性,但作者认为采用 量化布尔公式 减少这种方法具有明显的优势。
May, 2018
结构化 d-DNNF、SDD 和 OBDD 之间存在可处理性转换和简洁性差距的问题,我们通过实验证明结构化 d-DNNF 不支持多项式时间的取反、析取和存在量词操作,并且存在一些函数,其具有等价的多项式大小的结构化 d-DNNF,但没有等价的 SDD 表示。我们还通过对算术电路(AC)的研究,将这个结果推广到 PSDD 和结构化 d-DNNF 的单调 AC 类似物之间,从而展示了简洁性差距。
Feb, 2024
通过语法特征,我们为 Sentential Decision Diagrams(SDDs)推导出具有一般性的修订算法,并呈现了一个特殊的程序,以便于修订任务的直接操作。
Jan, 2022
本文研究了用于准确计算布尔公式的确定性决策图 (d-DNNF) 表示法,将其转换为自由二叉决策图 (FBDD) 用于提供计算上限,并证明了决策 - DNNF 的指数下限,从而提高了关联概率数据库的计算效率。
Sep, 2013