Linear Fold and Tree Fold in Creation of Binary Decision Diagrams of Standard Benchmarks

A Binary Decision Diagram (BDD) is one of possible representations of a Boolean function. Unlike other representations, such as truth table or symbolic expression, it is able to represent functions of many variables in an efficient way and can be simply processed on a computer. In case of a Boolean function that can be decomposed into smaller functions joined by an associative operation, the final BDD can be obtained by creating BDDs of smaller functions and then by their merging using the associative operation. Since the operation is associative, the merging can be done in two principal ways. The first one is linear fold, in which the BDDs of smaller functions are processed sequentially. This includes strategies known as left fold (processing from left to right), right fold (processing from right to left), and random linear fold (sequential processing in random order). The second one is tree fold, which processes the BDDs of smaller functions in a hierarchic way. Although, the number of processed BDDs is same in both types of fold, it has been shown that time needed for processing BDDs using linear fold and tree fold can be very different. To further investigate this interesting result, we focus in this paper on creation of BDDs of Boolean functions defined in standard set of benchmarks known as IWLS'93 and compare time that is needed for creation of BDDs representing these functions using linear fold and tree fold.