Template-Type: ReDIF-Paper 1.0
Author-Name: Bioch, J.C.
Author-Name-Last: Bioch
Author-Name-First: Cor
Title: The Algorithmic Complexity of Modular Decomposition
Abstract: 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 func tions is NP-complete. Moreover, we introduce the so called generalized Shannon decomposition of a Boolean functions as an efficient tool for proving theorems on Boolean function decompositions.
Creation-Date: 2001-06-14
File-URL: https://repub.eur.nl/pub/99/erimrs20010614160249.pdf
File-Format: application/pdf
Series: RePEc:ems:eureri
Number: ERS-2001-30-LIS
Classification-JEL: C69, M, M11, R4
Keywords: Boolean functions, computational complexity, decomposition algorithm, modular decomposition, substitution decomposition
Handle: RePEc:ems:eureri:99