检索结果-内蒙古大学图书馆

On Preprocessing Techniques and Their Impact on propositional model counting

JOURNAL OF AUTOMATED REASONING 2017年第4期58卷 413-481页

作者： Lagniez, Jean-Marie Marquis, Pierre CRIL CNRS Lens France Univ Artois Lens France

This paper is concerned with preprocessing techniques for propositional model counting. We have considered several elementary preprocessing techniques: backbone identification, occurrence reduction, vivification, as well as equivalence, AND and XOR gate identification and replacement. All those techniques have been implemented in a preprocessor pmc, freely available on the Web. In order to assess the benefits which can be gained by taking advantage of pmc, we performed many experiments, based on benchmarks coming from several data sets. More precisely, we made a differential evaluation of each elementary preprocessing technique in order to evaluate its impact on the number of variables of the instance, its size, as well as the treewidth of its primal graph. We also considered two combinations of preprocessings: , based on equivalence-preserving techniques only, and , which additionally exploits techniques preserving only the number of models. Several approaches to model counting have also been considered downstream in our experiments: "direct" model counters, including the exact ones Cachet, sharpSAT, and an approximate one SampleCount, as well as the compilation-based model counters C2D, Dsharp, SDD and cnf2obdd have been used. The experimental results we have obtained show that each elementary preprocessing technique is useful, and that some synergetic effects can be achieved by combining them.

关键词： propositional model counting #SAT Preprocessing Knowledge compilation

来源：评论

学校读者我要写书评

暂无评论

Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width

Better Algorithms for Satisfiability Problems for Formulas o...

引用

35th International Symposium on Mathematical Foundations of Computer Science

作者： Ganian, Robert Hlineny, Petr Obdrzalek, Jan Masaryk Univ Fac Informat Brno Czech Republic

We provide a parameterized algorithm for the propositional model counting problem #SAT, the runtime of which has a single-exponential dependency on the rank-width of the signed graph of a formula. That is, our algorithm runs in time O (t(3) . 2(3t(t+1)/2) . vertical bar phi vertical bar) for a width-t rank-decomposition of the input phi, and can be of practical interest for small values of rank-width. Previously, analogical algorithms have been known - e.g. [Fischer, Makowsky, and Ravve] - with a single-exponential dependency on the clique-width k of the signed graph of a formula with a given k-expression. Our algorithm presents an exponential runtime improvement over the worst-case scenario of the previous one, since clique-width reaches up to exponentially higher values than rank-width. We also provide an algorithm for the MAX-SAT problem along the same lines.

关键词： propositional model counting satisfiability rank-width clique-width parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width

Better Algorithms for Satisfiability Problems for Formulas o...

引用

30th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)

作者： Ganian, Robert Hlineny, Petr Obdrzalek, Jan Masaryk Univ Fac Informat Brno Czech Republic

ISBN: (纸本)9783939897231

We provide a parameterized polynomial algorithm for the propositional model counting problem #SAT, the runtime of which is single-exponential in the rank-width of a formula. Previously, analogous algorithms have been known - e.g. [Fischer, Makowsky, and Ravve] - with a single-exponential dependency on the clique-width of a formula. Our algorithm thus presents an exponential runtime improvement (since clique-width reaches up to exponentially higher values than rank-width), and can be of practical interest for small values of rank-width. We also provide an algorithm for the MAX-SAT problem along the same lines.

关键词： propositional model counting satisfiability rank-width clique-width parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Knowledge Compilation Languages as Proof Systems 1

引用

22nd International Conference on Theory and Applications of Satisfiability Testing (SAT)

作者： Capelli, Florent Univ Lille INRIA UMR 9189 CRIStAL Ctr Rech Informat Signal & Automat Lille F-59000 Lille France

ISBN: (数字)9783030242589

ISBN: (纸本)9783030242589;9783030242572

In this paper, we study proof systems in the sense of Cook-Reckhow for problems that are higher in the Polynomial Hierarchy than coNP, in particular, #SAT and maxSAT. We start by explaining how the notion of Cook-Reckhow proof systems can be apply to these problems and show how one can twist existing languages in knowledge compilation such as decision DNNF so that they can be seen as proof systems for problems such as #SAT and maxSAT.

关键词： Knowledge compilation propositional Proof Complexity propositional model counting maxSAT

来源：评论

学校读者我要写书评

暂无评论

An Improved GPU-Based SAT model Counter 25th

An Improved GPU-Based SAT Model Counter

引用

25th International Conference on the Principles and Practice of Constraint Programming (CP)

作者： Fichte, Johannes K. Hecher, Markus Zisser, Markus Tech Univ Dresden Dresden Germany TU Wien Vienna Austria Univ Potsdam Potsdam Germany

ISBN: (纸本)9783030300487

In this paper, we present and evaluate a new parallel propositional model counter, called gpusat2, which is based on dynamic programming (DP) on tree decompositions using log-counters. gpusat2 extends its predecessor by a novel architecture for DP that includes using customized tree decompositions, storing solutions to parts of the input instance during the computation variably in arrays or binary search trees, and compressing solution parts. In addition, we avoid data transfer between the RAM and the VRAM whenever possible and employ extended preprocessing by means of state-of-the-art preprocessors for propositional model counting. Our novel architecture allows gpusat2 to be competitive with modern model counters when we also take preprocessing into consideration. As a side result, we observe that state-of-the-art preprocessors allow to produce tree decompositions of significantly smaller width.

关键词： propositional model counting Dynamic programming Parameterized algorithmics Bounded treewidth

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：