New multivalued functional decomposition algorithms based on MDDs

This paper presents two new functional decomposition partitioning algorithm s that use multivalued decision diagrams (MDDs). MDDs are an exceptionally good representation for generalized decomposition because they are canonica l and they can represent very large functions. Algorithms developed in this paper are for Boolean/multivalued input and output, completely/incompletel y specified functions with application to logic synthesis, machine learning , data mining and knowledge discovery in databases. We compare the run-time s and decision diagram sizes of our algorithms to existing decomposition pa rtitioning algorithms based on decision diagrams. The comparisons show that our algorithms are faster and do not result in exponential diagram sizes w hen decomposing functions with small bound sets.