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

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