Abstract
The paper presents a variable elimination method for computing the probability of a cnf query over a belief network. We present a bucket-elimination algorithm whose complexity is controlled by the induced-width of the moral graph combined with the interaction graph of the cnf. We show that the algorithm can be easily extended to answer a host of additional cnf-related queries such as finding the most probable model of the cnf theory, or finding the most probable tuple satisfying the cnf theory, as well as belief assessment conditioned on disjunctive type observations.