Size of OBDD representation of 2-level redundancies functions
We consider an explicit boolean function depending on n = (i + 1)j variables encoding 2-level cascade redundancies in critical systems. We establish lower and upper bounds on the size of its OBDD representation. The exact lower bound of this function is comprised between Omega (2(min(i/2, 1ptj/2))) and O(2(min(i, 1 ptj)))). The upper bound is Omega (2(2)(i(1 ptj-2log)(i))). We further show that, when one of the parameters i or j is constant, this function admits OBDDs whose size is polynomial in other parameter. The latter result is constructive, and we show variable orderings that witness this polynomial size. (C) 2001 Elsevier Science B.V. All rights reserved.
boolean functions binary decision diagrams size complexity reliability