ProCount: weighted projected model counting with graded project-join trees

DOI10.1007/978-3-030-80223-3_11MaRDI QIDQ2118296zbMATH OpenOpenAlexFDO

Authors Jeffrey M. Dudek, Vu H. N. Phan, Moshe Y. Vardi

Publication date 22 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-80223-3_11

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Exploiting treewidth for projected model counting and its limits
• Projected model counting: beyond independent support
• Solving projected model counting by utilizing treewidth and its limits
• Exploiting structure in weighted model counting approaches to probabilistic inference
• On probabilistic inference by weighted model counting
• Fast and flexible probabilistic model counting
• Weighted model counting on the GPU by exploiting small treewidth
• A new probabilistic algorithm for approximate model counting
• Treewidth and counting projected answer sets

Cites work

• \(\#{\exists}\mathrm{SAT}\): projected model counting
• Algorithms for propositional model counting
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Bucket elimination: A unifying framework for reasoning
• DRAT-trim: Efficient Checking and Trimming Using Expressive Clausal Proofs
• DYNAMIC PROGRAMMING AND A NEW FORMALISM IN THE THEORY OF INTEGRAL EQUATIONS
• Expansion-based QBF solving on tree decompositions
• Exploiting structure in quantified formulas
• Exploiting treewidth for projected model counting and its limits
• Graph bisection with Pareto optimization
• Graph minors. X: Obstructions to tree-decomposition
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 2084701 (Why is no real title available?)
• scientific article; zbMATH DE number 2243356 (Why is no real title available?)
• Machine learning. A probabilistic perspective
• Ordered binary decision diagrams and the Davis-Putnam procedure
• Positive-instance driven dynamic programming for treewidth
• Random generation of combinatorial structures from a uniform distribution
• SATzilla: portfolio-based algorithm selection for SAT
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Solving \#SAT and Bayesian inference with backtracking search
• Symbolic techniques in satisfiability solving
• Taming high treewidth with abstraction, nested dynamic programming, and database technology
• Treewidth: computational experiments
• Which problems have strongly exponential complexity?

Cited in

(3)

• Solving projected model counting by utilizing treewidth and its limits
• Generating random instances of weighted model counting. An empirical analysis with varying primal treewidth
• ZDD Boolean synthesis

Describes a project that uses

Uses Software

• PMTK
• DRAT-trim
• GANAK
• Sylvan
• SATzilla
• htd

This page was built for publication: ProCount: weighted projected model counting with graded project-join trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118296)