Document Type

Conference Proceeding

Publication Date



Logic circuits, Computer algorithms, Machine learning


We present an implicit approach to solve problems arising in decomposition of incompletely specified multi-valued functions and relations. We introduce a new representation based on binaryencoded multi-valued decision diagrams (BEMDDs). This representation shares desirable properties of MDDs, in particular, compactness, and is applicable to weakly-specified relations with a large number of output values. This makes our decomposition approach particularly useful for data mining and machine learning. Using BEMDDs to represent multi-valued relations we have developed two complementary input support minimization algorithms. The first algorithm is efficient when the resulting support contains almost all initial variables; the second is efficient when it contains only a few. We propose a simple heuristic measure to choose which algorithm to use. Numerical results over a set of multi-valued benchmarks provide experimental evidence for the efficiency of our approach.


Originally presented at the 4th International Workshop on Boolean Problems, September 2000, Freiberg, Germany, and subsequently included in its proceedings.

Persistent Identifier