Abstract
This paper explores algorithms for processing probabilistic and deterministic information when the former is represented as a belief network and the latter as a set of boolean clauses. The motivating tasks are 1. evaluating belief networks having a large number of deterministic relationships and 2. evaluating probabilities of complex boolean queries or complex evidence information over a belief network. We present and analyze a variable elimination algorithm that exploits both types of information, and provide empirical evaluation demonstrating its computational benefits.