Abstract
The paper introduces mixed networks, a new framework for expressing and reasoning with probabilistic and deterministic information. The framework combines belief networks with constraint networks, defining the semantics and graphical representation. We also introduce a new linear space search algorithm based on an AND/OR search space. This provides the basis for understanding the benefits of processing the constraint information separately, resulting in the pruning of the search space. When the constraint part is tractable or has a small number of solutions, using the mixed representation can be exponentially more effective than using pure belief networks in which constraints are modeled as conditional probability tables. The experimental results we provide confirm that even weak forms of constraint propagation such as forward checking are more effective than using the auxiliary network.