Bibliographic Details
| Title: |
Exact OBDD Bounds for Some Fundamental Functions. |
| Authors: |
Bollig, Beate1 beate.bollig@uni-dortmund.de, Range, Niko1 niko@range.at, Wegener, Ingo |
| Source: |
Theory of Computing Systems. Aug2010, Vol. 47 Issue 2, p593-609. 17p. 2 Diagrams, 19 Charts. |
| Subjects: |
Computational complexity, Dynamic data exchange, Data transmission systems, Boolean algebra, Graphic methods, Computer-aided design, Relation algebras |
| 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. [ABSTRACT FROM AUTHOR] |
|
Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
