The complexity of modular decomposition of Boolean functions
Discrete Applied Mathematics , Volume 149 - Issue 1-3 p. 1- 13
Modular decomposition is a thoroughly investigated topic in many areas such as switching theory, reliability theory, game theory and graph theory. We propose an O(mn)-algorithm for the recognition of a modular set of a monotone Boolean function f with m prime implicants and n variables. Using this result we show that the computation of the modular closure of a set can be done in time O(mn2). On the other hand, we prove that the recognition problem for general Boolean functions is coNP-complete. Moreover, we introduce the so-called generalized Shannon decomposition of a Boolean function as an efficient tool for proving theorems on Boolean function decompositions.
|, , , , , , , ,|
|Discrete Applied Mathematics|
|Organisation||Erasmus School of Economics|
Bioch, J.C. (2005). The complexity of modular decomposition of Boolean functions. Discrete Applied Mathematics, 149(1-3), 1–13. doi:10.1016/j.dam.2003.12.010