Exact OBDD Bounds for Some Fundamental Functions |
| |
Authors: | Beate Bollig Niko Range Ingo Wegener |
| |
Affiliation: | 1. LS2 Informatik, TU Dortmund, 44221, Dortmund, Germany
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|