Investigation of a New Compressed Representation of Boolean Functions

CCR-9986308 代表，托马斯W。 威斯康星大学麦迪逊分校 一种新的布尔函数压缩表示的研究 拟议项目的目标是促进国家的发展， 通过研究符号模型检查的属性来进行符号模型检查的艺术 布尔函数的一种新的压缩表示，称为 CFLOBDD，它是现在标准的Ordered 二进制决策图（OBDDs）。 CFLOBDD共享许多 OBDDs的良好特性，但可能导致数据结构 体积小得多--比OBDD小得多， 事实 也就是说，OBDD是一种数据结构， 在这种情况下， 布尔函数的表示（即，较 函数的决策树的大小）。 相比之下，一 CFLOBDD --同样，在最好的情况下--产生双指数 布尔值表示法的大小的减小 功能 虽然不是每个布尔函数都有如此高的 压缩表示，该项目与看到多远，这 想法是可以推动的。 希望双指数压缩 是一种工具，它将（a）允许进行更多的核查， 更快，以及（B）允许攻击更大的验证问题 比以往任何时候都要多

CCR-9986308 Reps, Thomas W. University of Wisconsin-Madison Investigation of a New Compressed Representation of Boolean Functions The goal of the proposed project is to advance the state of the art in symbolic model checking by investigating the properties of a new compressed representation of Boolean functions, called CFLOBDDs, which are an alternative to the now-standard Ordered Binary Decision Diagrams (OBDDs). CFLOBDDs share many of the good properties of OBDDs, but can lead to data structures of drastically smaller size -- exponentially smaller than OBDDs, in fact. That is, an OBDD is a data structure that -- in the best case -- yields an exponential reduction in the size of the representation of a Boolean function (i.e., compared with the size of the decision tree for the function). In contrast, a CFLOBDD -- again, in the best case -- yields a doubly exponential reduction in the size of the representation of a Boolean function. Although not every Boolean function has such a highly compressed representation, the project with see how far this idea can be pushed. The hope is that doubly-exponential compression is a tool that would (a) permit verification to be performed much faster, and (b) allow much larger verification problems to be attacked than has heretofore been possible.