Two approximate algorithms for model counting

DOI10.1016/j.tcs.2016.04.047zbMath1356.68110OpenAlexW2413589572MaRDI QIDQ507433

Minghao Yin, Jingli Wu, Jinyan Wang

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

resolution principlepropositional satisfiabilitymodel countingextension rule

Mathematics Subject Classification ID

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

Uses Software

• Walksat
• sharpSAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Planning as satisfiability: heuristics
• Leveraging belief propagation, backtrack search, and statistics for model counting
• Random generation of combinatorial structures from a uniform distribution
• Approximate inclusion-exclusion
• Inclusion-exclusion: exact and approximate
• Theorem proving based on the extension rule
• Towards a theory of random walk planning: Regress factors, fair homogeneous graphs and extensions
• Exploiting Structure in Weighted Model Counting Approaches to Probabilistic Inference
• Solving #SAT Using Extension Rules
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• A machine program for theorem-proving
• Theory and Applications of Satisfiability Testing

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