Approximate model counting via extension rule

DOI10.1007/978-3-319-19647-3_22MaRDI QIDQ3452569zbMATH OpenOpenAlexFDO

Authors Jinyan Wang, Minghao Yin, Jingli Wu

Publication date 12 November 2015

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-19647-3_22

zbMATH Keywords

extension rulemodel countingpropositional satisfiabilityresolution principle

Mathematics Subject Classification ID

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

Recommendations

• Two approximate algorithms for model counting
• Solving \#SAT using extension rules
• Theory and Applications of Satisfiability Testing
• A new probabilistic algorithm for approximate model counting
• Model counting: a new stategy for obtaining good bounds

Cites work

• 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
• scientific article; zbMATH DE number 1315584 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• scientific article; zbMATH DE number 956863 (Why is no real title available?)
• 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

(4)

• New width parameters for model counting
• Counting extensional differences in BC-learning
• Solving \#SAT using extension rules
• Two approximate algorithms for model counting

Describes a project that uses

Uses Software

• Walksat
• sharpSAT

This page was built for publication: Approximate model counting via extension rule

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