کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431303 688499 2014 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Counting solutions to CSP using generating polynomials
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Counting solutions to CSP using generating polynomials
چکیده انگلیسی

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
نویسندگان
, ,