We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Exact OBDD Bounds for Some Fundamental Functions.
- Authors
Bollig, Beate; Range, Niko; Wegener, Ingo
- 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.
- Subjects
COMPUTATIONAL complexity; DYNAMIC data exchange; DATA transmission systems; BOOLEAN algebra; GRAPHIC methods; COMPUTER-aided design; RELATION algebras
- Publication
Theory of Computing Systems, 2010, Vol 47, Issue 2, p593
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-009-9217-3