Modular Decomposition of Boolean Functions
2002-04-08
Research Paper
| Related Files |
|---|
View PDF Version
(erimrs20020408085344.pdf, 0.6MB) |
Modular decomposition is a thoroughly investigated topic in many areas such as switching theory, reliability theory, game theory and graph theory. Most appli- cations can be formulated in the framework of Boolean functions. In this paper we give a uni_ed treatment of modular decomposition of Boolean functions based on the idea of generalized Shannon decomposition. Furthermore, we discuss some new results on the complexity of modular decomposition. 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 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.
- computational complexity
- Boolean functions
- decomposition algorithm
- substitution decomposition
- reliability theory
- C69 : Mathematical Methods and Programming: Other
- M : Business Administration and Business Economics; Marketing; Accounting
- R4 : Transportation Systems
- M11 : Production Management
- management
- theory
- research
- loop supply chains
- decomposition
- function
- business
- boolean
- wagelman
- system
- bioch
- albert
- van den bergh
- van den berg
- series
- scheduling
- richard
- report
- refrigerators harold krikke
- kaymak
