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

fYear

1993

fDate

24-27 May 1993

Firstpage

126

Lastpage

131

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)³. In the case in which a random function has a single disjunctive decomposition, the time complexity becomes of the order n³mⁿ. 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;

fLanguage

English

Publisher

ieee

Conference_Titel

Multiple-Valued Logic, 1993., Proceedings of The Twenty-Third International Symposium on

Conference_Location

Sacramento, CA

Print_ISBN

0-8186-3350-6

Type

conf

DOI

10.1109/ISMVL.1993.289570

Filename

289570