کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9655177 | 684860 | 2005 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The complexity of modular decomposition of Boolean functions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The complexity of modular decomposition of Boolean functions The complexity of modular decomposition of Boolean functions](/preview/png/9655177.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 149, Issues 1â3, 1 August 2005, Pages 1-13
Journal: Discrete Applied Mathematics - Volume 149, Issues 1â3, 1 August 2005, Pages 1-13
نویسندگان
Jan C. Bioch,