Two approximate algorithms for model counting

DOI10.1016/J.TCS.2016.04.047zbMATH Open1356.68110OpenAlexW2413589572MaRDI QIDQ507433FDOQ507433

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