Title :
A fast algorithm for the disjunctive decomposition of m-valued functions. II. Time complexity analysis
Author :
Abugharbieh, Sami B. ; Lee, Samuel C.
Author_Institution :
Sch. of Electr. Eng., Oklahoma Univ., Norman, OK, USA
Abstract :
For part I see ibid., p.118-25. The time complexity of the fast algorithm for the disjunctive decomposition of m-valued functions, proposed in part I is studied. A probabilistic approach is used to estimate the time complexity for random m-valued functions, where several statistical properties of such functions are obtained and used in the analysis. It is shown that the time complexity for random functions is of the order of (nm)3. In the case in which a random function has a single disjunctive decomposition, the time complexity becomes of the order n3 mn. The algorithm was simulated on a digital computer. The experimental results are in agreement with the theoretical predictions
Keywords :
computational complexity; many-valued logics; switching functions; algorithm; disjunctive decomposition; fast algorithm; m-valued functions; probabilistic approach; random function; time complexity; Algebra; Algorithm design and analysis; Bismuth; Computational modeling; Computer simulation; Partitioning algorithms; Testing; Zinc;
Conference_Titel :
Multiple-Valued Logic, 1993., Proceedings of The Twenty-Third International Symposium on
Conference_Location :
Sacramento, CA
Print_ISBN :
0-8186-3350-6
DOI :
10.1109/ISMVL.1993.289570