How many Decomposition Types do we need ?

Decision Diagrams (DDs) are used in many applications in CAD. Various types of DDs, e.g. BDDs, FDDs, KFDDs, differ by their decomposition types. In this paper we investigate the different decomposition types and prove that there are only three that really help to reduce the size of DDs. 1 Introduction Decision Diagrams (DDs) are successfully applied in many fields of design automation, e.g. [17, 4, 1, 14, 7, 24, 11, 2, 9]. The most popular type of DD is the Ordered Binary Decision Diagram (OBDD) allowing efficient representation and manipulation of Boolean functions [5]. The more recent techniques have made it possible to handle (some) large functions without any basic variation of the OBDD concept itself. The dynamic variable ordering with sifting introduced by Rudell [21] allows to represent examples which could not be represented by any previous heuristic methods. Moreover, the variable ordering in [21] is handled by the package itself, alleviating the need for variable ordering ..