Probabilistic Arc Consistency: A Connection between Constraint Reasoning
  and Probabilistic Reasoning
  We document a connection between constraint reasoning and probabilistic
reasoning. We present an algorithm, called {em probabilistic arc consistency},
which is both a generalization of a well known algorithm for arc consistency
used in constraint reasoning, and a specialization of the belief updating
algorithm for singly-connected networks. Our algorithm is exact for singly-
connected constraint problems, but can work well as an approximation for
arbitrary problems. We briefly discuss some empirical results, and related
methods.
