Design and implementation of multiple-valued decision diagrams based on a binary decision diagram package

Many problems can be stated naturally using variables that have multiple values. Functions defined on these variables can also take on values from a discrete set. Compact representation and efficient manipulation of such multi-valued functions are key to the design of efficient algorithms that advance the frontier of the problems that can be solved exactly. Binary decision diagrams are such a compact representation for problems involving binary variables. It has long been supposed that since multi-valued functions can be represented as a binary input binary multi-output function, a simple relation exists between the two to map the number of nodes from a binary diagram into its resulting multi-valued diagram.;Working with this premise we will show why there is no simple relationship between the two for all general functions. The actual algorithm for the binary output sub-cases will then be demonstrated and formally defined. This algorithm will then be used to give an upper limit on the number of nodes that can be generated in the binary case from the simplest of the multi-valued diagrams. Furthermore we will show its impact on some benchmark functions.;This paper will explore just that phenomenon and formally define an algorithm that returns the number of nodes in the multi-valued diagram. This algorithm, it turns out, is only valid for multi-valued functions that have a binary output. Although this property has been observed and documented before, it has been assumed that the design can easily be extended to more general multi-valued functions. That is not the case, since the method by which subgraph merging operates differs between the binary and multi-valued cases. This causes a breakdown of the direct mapping property that has been observed and documented in the binary output case.