结构化的 d-DNNF 不封闭于否定
内容提要
本文综述知识编译中SDD、DNNF、OBDD等表示语言的研究，证明SDD比OBDD更简洁并解决开放问题；提出CNF转DNNF算法及OBDD转DNNF线性算法；给出SDD指数下界；研究神经网络决策函数编译与鲁棒性验证；提出CCDD新语言及SDD修订算法。
延伸解读
SDD 与 OBDD 的简洁性对比
文章指出，SDD 在表示布尔函数时比 OBDD 更简洁，这一结论解决了知识编译中的一个开放性问题。对于读者而言，这意味着在需要紧凑表示布尔函数的场景中，SDD 可能提供比传统 OBDD 更优的空间效率。但文章也提到，SDD 的简洁性优势并非绝对，其实际表现取决于具体函数和问题结构，因此在实际应用中需结合具体需求评估。
d-DNNF 的封闭性限制
文章标题指出“结构化的 d-DNNF 不封闭于否定”，这意味着对 d-DNNF 表示进行否定操作后，结果可能无法保持相同的结构化形式。这一性质对知识编译和推理系统设计有重要影响：如果系统需要频繁处理否定，直接使用 d-DNNF 可能导致表示膨胀或需要额外转换。读者在设计基于 d-DNNF 的算法时，应留意否定操作可能带来的表示复杂度变化。
神经网络验证中的编译方法
文章探讨了将二进制神经网络的决策函数编译为 OBDD 或命题决策图等表示形式，并用于验证鲁棒性。实验表明，命题决策图能获得神经网络的紧凑表示，且不同网络在准确度相近时鲁棒性可能差异显著。这提示读者，在评估神经网络时，除了准确度，还应关注其鲁棒性，而编译方法为形式化验证提供了一种可行途径，但可能受限于网络规模和结构。
CCDD 新语言的潜力与定位
文章提出了一种新的表示语言 CCDD，并声称其在模型计数和一致采样上优于现有的 Decision-DNNF、SDD 和 OBDD 编译器。对于关注知识编译工具的研究者，CCDD 可能是一个有前景的替代方案，尤其是在需要高效计数或采样的任务中。然而，文章未提供与其他语言在更广泛任务上的详细对比，因此其通用性仍需进一步验证。
Q&A
SDD 和 OBDD 在表示布尔函数时哪个更简洁？
SDD 比 OBDD 更简洁。文章证明了在布尔函数的表示中，SDD 比 OBDD 更简洁，这一结论解决了知识编译中的一个开放性问题。
如何将 CNF 转换为 DNNF？
文章提出了将任何合取范式（CNF）转化为 DNNF 的算法，并提供了其空间和时间复杂度上的结构保证。
OBDD 可以转换为 DNNF 吗？时间复杂度如何？
可以。文章介绍了将有序二叉决策图（OBDD）表示的命题理论转换为等价的 DNNF 的线性时间算法。
SDD 在表示某些布尔函数时是否有指数下界？
是的。文章给出了关于知识编译到 SDD 和 DNNF 形式的新下限，并利用 SDD 大小与最佳划分通信复杂度的关系证明了一类大型问题的 SDD 大小的指数下限。
如何将神经网络的决策函数编译成可行的表示形式？
文章研究了将二进制神经网络的决策函数编译成有序二进制决策图和命题决策图等可行表示形式，并讨论了使用这些表示形式来验证神经网络的鲁棒性和计算期望鲁棒性的方法。此外，还提出了一种基于伪多项式时间算法编译单个神经元的高效方法。
CCDD 是什么？它有什么优势？
CCDD 是一种新的表示语言。文章利用其支持的多项式算法在模型计数和一致采样上显著改进于目前最先进的 Decision-DNNF、SDD 和 OBDD [AND] 编译器，以及在 CNF 上开发模型计数器和一致采样器。
SDD 的修订算法是如何实现的？
文章通过语法特征为 Sentential Decision Diagrams（SDDs）推导出具有一般性的修订算法，并呈现了一个特殊的程序，以便于修订任务的直接操作。
