  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 the AND/OR search space for
graphical models, and develop a new linear space search algorithm. 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 which odel constraints as conditional probability tables.
