کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429217 | 687096 | 2007 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the fixed-parameter tractability of the equivalence test of monotone normal forms
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We consider the problem Monet—given two monotone formulas φ in DNF and ψ in CNF, decide whether they are equivalent. While Monet is probably not coNP-hard, it is a long standing open question whether it has a polynomial time algorithm and thus belongs to P. In this paper we examine the parameterized complexity of Monet. We show that Monet is in FPT by giving fixed-parameter algorithms for different parameters.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 103, Issue 4, 16 August 2007, Pages 163-167
Journal: Information Processing Letters - Volume 103, Issue 4, 16 August 2007, Pages 163-167