  Probabilistic inference algorithms for finding the most probable explanation,
the maximum aposteriori hypothesis, and the maximum expected utility and for
updating belief are reformulated as an elimination--type algorithm called
bucket elimination. This emphasizes the principle common to many of the
algorithms appearing in that literature and clarifies their relationship to
nonserial dynamic programming algorithms. We also present a general way of
combining conditioning and elimination within this framework. Bounds on
complexity are given for all the algorithms as a function of the problem's
structure.
