Exact OBDD Bounds for Some Fundamental Functions
Exact OBDD Bounds for Some Fundamental Functions
复制标题
某些基本函数的精确 OBDD 界限
DOI：
10.1007/s00224-009-9217-3
复制
发表时间：
2008
影响因子：
0.5
通讯作者：
I. Wegener
中科院分区：
文献类型：
--
作者：
Beate Bollig;Niko Range;I. Wegener
有序二元决策图 (OBDD) 是当今最常见的动态数据结构或布尔函数表示类型之一。许多应用领域包括验证、模型检查、计算机辅助设计、关系代数和符号图算法。尽管布尔函数 OBDD 大小的许多指数下界是已知的，但只有少数函数的 OBDD 大小是渐近精确已知的。本文确定了基本功能多路复用器的准确 OBDD 大小以及 n 位数字的加法。
Ordered binary decision diagrams (OBDDs) are nowadays one of the most common dynamic data structures or representation types for Boolean functions. Among the many areas of application are verification, model checking, computer aided design, relational algebra, and symbolic graph algorithms. Although many exponential lower bounds on the OBDD size of Boolean functions are known, there are only few functions where the OBDD size is asymptotically known exactly. In this paper the exact OBDD sizes of the fundamental functions multiplexer and addition of n-bit numbers are determined.