Mod-2-OBDDs—A data structure that generalizes EXOR-sum-of-products and ordered binary decision diagrams
Mod-2-OBDDs—A data structure that generalizes EXOR-sum-of-products and ordered binary decision diagrams
复制标题
Mod-2-OBDD - 一种概括 EXOR 乘积和和有序二元决策图的数据结构
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
C. Meinel
中科院分区：
文献类型：
--
作者：
Jordan Gergov;C. Meinel
我们提出了一个布尔操纵的数据结构 - mod-2-obdds-大大扩展了ESOP（exor-of-affuctucts）和OBDD（有序的二进制决策图）。具有指数尺寸最佳的ESOP（甚至是多级驱动器表达式）和/或OBDD的实用性功能的布尔功能，可以用（低度）多项式大小mod-2-obdds表示。可以使用MOD-2-OBDD进行操作，定量，组成，至少与OBDD一样有效。实际上，由于通常，布尔函数的最小MOD-2-OBDD代理的大小比最佳OBDD代理的大小通常要小（有时甚至小），因此效率的提高相当可观。此外，可以在恒定时间内（1）以恒定的时间来执行exor操作以及补充。但是，恒定时间的经费操作的价格是mod-2-obdd-presentation的构成性。为了允许对Mod-2-Obdds进行有效分析，我们提出了一个快速的概率等效测试，具有MOD-2-OBDD（以及，因此，对于ESOP）的单侧误差概率（因此，对于ESOP），仅执行线性许多算术算术运营。
We present a data structure for Boolean manipulation-the Mod-2-OBDDs-that considerably extends ESOPs (EXOR-sum-of-products) as well as OBDDs (ordered binary decision diagrams). There are Boolean functions of practical interest which have exponential size optimal ESOPs (even multilevel EXOR-expressions) and/or OBDDs that can be represented by (low degree) polynomial size Mod-2-OBDDs.We show that Boolean manipulation tasks such as apply operation, quantification, composition can be performed with Mod-2-OBDDs at least as efficient as with OBDDs. Indeed, since the size of a minimal Mod-2-OBDD-representation of a Boolean function is, in general, smaller (sometimes even exponentially smaller) than the size of an optimal OBDD-representation, the increase in efficiency is considerable. Moreover, EXOR-operations as well as complementations can be performed in constant timeO (1).However, the price of constant time EXOR-apply operations is the canonicity of the Mod-2-OBDD-representation. In order to allow in spite of this fact efficient analysis of Mod-2-OBDDs we present a fast probabilistic equivalence test with one-sided error probability for Mod-2-OBDDs (and, hence, for ESOPs) which performs only linear many arithmetic operations.