کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657713 | 690091 | 2005 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On converting CNF to DNF
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On converting CNF to DNF On converting CNF to DNF](/preview/png/9657713.png)
چکیده انگلیسی
We study how big the blow-up in size can be when one switches between the CNF and DNF representations of Boolean functions. For a function f:{0,1}nâ{0,1}, cnfsize(f) denotes the minimum number of clauses in a CNF for f; similarly, dnfsize(f) denotes the minimum number of terms in a DNF for f. For 0⩽m⩽2n-1, let dnfsize(m,n) be the maximum dnfsize(f) for a function f:{0,1}nâ{0,1} with cnfsize(f)⩽m. We show that there are constants c1,c2⩾1 and ε>0, such that for all large n and all mâ[1εn,2εn], we have2n-c1(n/log(m/n))⩽dnfsize(m,n)⩽2n-c2(n/log(m/n)).In particular, when m is the polynomial nc, we get dnfsize(nc,n)=2n-θ(c-1(n/logn)).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 347, Issues 1â2, 30 November 2005, Pages 325-335
Journal: Theoretical Computer Science - Volume 347, Issues 1â2, 30 November 2005, Pages 325-335
نویسندگان
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener,