کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431303 | 688499 | 2014 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Counting solutions to CSP using generating polynomials
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Constraint Satisfaction Problems (CSPs) are ubiquitous in computer science and specifically in AI. This paper presents a method of solving the counting problem for a wide class of CSPs using generating polynomials. Analysis of our method shows that it is much more efficient than the classic dynamic programming approach. For example, in the case of #SAT, our algorithm improves a result of Samer and Szeider. The presented algorithms mostly use algebraic operations on multivariate polynomials, which allows application of known optimizations and makes it possible to use existing software to implement them easily.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 26, May 2014, Pages 89–97
Journal: Journal of Discrete Algorithms - Volume 26, May 2014, Pages 89–97
نویسندگان
Daniel Berend, Shahar Golan,