From Weighted to Unweighted Model Counting
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 689-694.
Abstract
The recent surge of interest in reasoning about probabilistic graphical models has led to the development of various techniques for probabilistic reasoning. Of these, techniques based on weighted model counting are particularly interesting since they can potentially leverage recent advances in unweighted model counting and in propositional satisfiability solving. In this paper, we present a new approach to weighted model counting via reduction to unweighted model counting. Our reduction, which is polynomial-time and preserves the normal form (CNF/DNF) of the input formula, allows us to exploit advances in unweighted model counting to solve weighted model counting instances. Experiments with weighted model counters built using our reduction indicate that these counters performs much better than a state-of-the-art weighted model counter.
@inproceedings{ijcai2015p103,
title = {From Weighted to Unweighted Model Counting},
author = {Chakraborty, Supratik and Fried, Dror and Meel, Kuldeep S. and Vardi, Moshe Y.},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {689--694},
year = {2015},
month = {7},
note = {Main Track},
url = {https://ijcai.org/proceedings/2015/103},
}
TY - CPAPER TI - From Weighted to Unweighted Model Counting AU - Chakraborty, Supratik AU - Fried, Dror AU - Meel, Kuldeep S. AU - Vardi, Moshe Y. T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 689 EP - 694 UR - https://ijcai.org/proceedings/2015/103 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
