Kuldeep S. Meel, Aditya A. Shrotri, Moshe Y. Vardi
TL;DR本文研究了命题模型计数问题,针对约束条件表达式分别为DNF公式和CNF公式分别介绍了Monte Carlo和基于哈希的计数技术,并提出了两种新算法技术:Symbolic Hashing和Stochastic Cell Counting,通过设计基于哈希的FPRAS for DNF counting提高了效率和应用价值。
Abstract
propositional model counting is a fundamental problem in artificial intelligence with a wide variety of applications, such as probabilistic inference, decision making under uncertainty, and probabilistic databases. Consequently, the problem is of theoretical as well as practical intere