The work on multi-valued decomposition for robotics applications is partially supported by an Intel grant for development of undergraduate robotics laboratories.
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.
Mishchenko, Alan, Craig Files, Marek Perkowski, Bernd Steinbach, and Christina Dorotska. "Implicit algorithms for multi-valued input support minimization." In 4th International Workshop on Boolean Problems, 2000.