Propagating belief functions through constraint systems

AbstractConstraint systems as used in temporal or spatial reasoning usually describe uncertainty by constraining variables into given sets. Viewing belief functions as random or uncertain sets, uncertainty in such models is quite naturally and more generally described by belief functions. Here a special class of constraint systems arising especially in numerical models underlying temporal and spatial reasoning is introduced. The computations are, as usual, plagued by combinatorial explosion in the general case. Structural properties of the knowledge base must therefore be exploited. It is shown that there are topological properties of a graph representing the model, which can be used to reduce computational complexity. Series-parallel graphs prove to be particularly simple with respect to computations. They play a role analogous to that of qualitative Markov trees in multivariate models. Moreover, the idea of reference elements leads to a natural hierarchical structuring of the knowledge base that permits computational simplifications