Two approximate algorithms for model counting

DOI10.1016/J.TCS.2016.04.047MaRDI QIDQ507433zbMATHOpenAlexFDO

Authors Jinyan Wang, Minghao Yin, Jingli Wu

Publication date 6 February 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.04.047

zbMATH Keywords

model countingpropositional satisfiabilityextension ruleresolution principle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Classical propositional logic (03B05) Mechanization of proofs and logical operations (03B35)

Recommendations

• Approximate model counting via extension rule
• Theory and Applications of Satisfiability Testing
• Algorithms for Propositional Model Counting
• Algorithms for propositional model counting
• A new probabilistic algorithm for approximate model counting

Cites work

• scientific article; zbMATH DE number 1315584 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• A machine program for theorem-proving
• Approximate inclusion-exclusion
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• Exploiting structure in weighted model counting approaches to probabilistic inference
• Inclusion-exclusion: exact and approximate
• Leveraging belief propagation, backtrack search, and statistics for model counting
• Planning as satisfiability: heuristics
• Probabilistic planning via heuristic forward search and weighted model counting
• Random generation of combinatorial structures from a uniform distribution
• Solving \#SAT and Bayesian inference with backtracking search
• Solving \#SAT using extension rules
• Theorem proving based on the extension rule
• Theory and Applications of Satisfiability Testing
• Towards a theory of random walk planning: regress factors, fair homogeneous graphs and extensions

Cited in

(19)

• Solving \#SAT using extension rules
• Model counting of monotone conjunctive normal form formulas with spectra
• Counting propositional models
• On hashing-based approaches to approximate DNF-counting
• Fast and flexible probabilistic model counting
• A new probabilistic algorithm for approximate model counting
• New width parameters for model counting
• Rounding meets approximate model counting
• Approximate counting in SMT and value estimation for probabilistic programs
• An exhaustive DPLL algorithm for model counting
• Theory and Applications of Satisfiability Testing
• Counting Models in Integer Domains
• Theory and Applications of Satisfiability Testing
• Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting
• Algorithms for propositional model counting
• Approximate model counting via extension rule
• Algorithms for Propositional Model Counting
• A study of symmetry breaking predicates and model counting
• \(\#{\exists}\mathrm{SAT}\): projected model counting

Describes a project that uses

Uses Software

• Walksat
• sharpSAT

This page was built for publication: Two approximate algorithms for model counting

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