Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-049 | 1st June 2007 00:00

Exact OBDD Bounds for some Fundamental Functions

RSS-Feed




TR07-049
Authors: Beate Bollig, Niko Range, Ingo Wegener
Publication: 5th June 2007 21:01
Downloads: 3533
Keywords: 


Abstract:

Ordered binary decision diagrams (OBDDs) are nowadays the most common
dynamic data structure or representation type for Boolean functions.
Among the many areas of application are verification, model checking,
computer aided design, relational algebra, and symbolic graph algorithms.
Although many even exponential lower bounds on the OBDD size of Boolean functions
are known, there are only few functions where the OBDD size is even asymptotically
known exactly.
In this paper the exact OBDD sizes of the fundamental
functions multiplexer and addition of n-bit numbers are determined.



ISSN 1433-8092 | Imprint