TIME COMPLEXITY ANALYSIS OF GENERALIZED DECOMPOSITION ALGORITHM

ABSTRACT: The time complexity of the fast algorithm for generalized disjunctive decomposition of an r-valued function is studied.The considered algorithm to find the best decomposition is based on the analysis of multiple-terminal multiple-valued decision diagrams. It is shown that the time complexity for random r-valued functions depends on the such restriction as the number n1 of inputs in the first level circuit. In the case where the best partition of input variables is searched with restriction the time complexity is reduced in several times. The algorithm was simulated on a digital computer. The experimental results are in agreement with the theoretical predictions. KEY WORDS: Decomposition algorithm, r-valued functions, generalized disjunctive decomposition. 1