A fast algorithm for the disjunctive decomposition of m-valued functions. I. The decomposition algorithm

摘要

The binary function decomposition algorithm of V. Shen et al. (1971) is generalized to m-valued functions with m<2. The necessary condition for the decomposability for m-valued functions is obtained and used in generating candidate bound sets. A fast method for testing the necessary condition using partial partition tables whereby the decomposability of the function can be determined for a randomly chosen function in (nm)/sup 3/ time is also obtained.