  This paper extends the applications of belief-networks to include the
revision of belief commitments, i.e., the categorical acceptance of a subset of
hypotheses which, together, constitute the most satisfactory explanation of the
evidence at hand. A coherent model of non-monotonic reasoning is established
and distributed algorithms for belief revision are presented. We show that, in
singly connected networks, the most satisfactory explanation can be found in
linear time by a message-passing algorithm similar to the one used in belief
updating. In multiply-connected networks, the problem may be exponentially hard
but, if the network is sparse, topological considerations can be used to render
the interpretation task tractable. In general, finding the most probable
combination of hypotheses is no more complex than computing the degree of
belief for any individual hypothesis. Applications to medical diagnosis are
illustrated.
