Implicit algorithms for multi-valued input support minimization

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 binary-encoded 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.