Hybrid Processing of Beliefs and Constraints
  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 beliefs
networks having a large number of deterministic relationships and2. evaluating
probabilities of complex boolean querie over a belief network. We propose a
parameterized family of variable elimination algorithms that exploit both types
of information, and that allows varying levels of constraint propagation
inferences. The complexity of the scheme is controlled by the induced-width of
the graph {em augmented} by the dependencies introduced by the boolean
constraints. Preliminary empirical evaluation demonstrate the effect of
constraint propagation on probabilistic computation.
