Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division

Takashi HORIYAMA  Shuzo YAJIMA  

IEICE TRANSACTIONS on Information and Systems   Vol.E81-D       pp.793-800
Publication Date: 1998/08/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Category: Algorithm and Computational Complexity
Boolean function,  division,  binary decision diagrams,  lower bound,  fooling set,  

Full Text: PDF>>
Buy this Article

An Ordered Binary Decision Diagram (OBDD) is a directed acyclic graph representing a Boolean function. The size of OBDDs largely depends on the variable ordering. In this paper, we show the size of the OBDD representing the i-th bit of the output of n-bit/n-bit integer division is Ω ( 2(n-i)/8 ) for any variable ordering. We also show that -OBDDs, -OBDDs and -OBDDs representing integer division has the same lower bounds on the size. We develop new methods for proving lower bounds on the size of -OBDDs, -OBDDs and -OBDDs.