Decision Diagrams for the Computation of Semiring Valuations

Abstract

Abstract. This paper describes an approach to computation in a semiringbased system, which includes semiring-based CSPs (in particular weighted CSPs, fuzzy CSPs and standard CSPs) as well as Bayesian networks. The approach to computation is based on what we call semiring-labelled decision diagrams (SLDDs), which are strongly related to binary decision diagrams and finite-state automata. SLDDs can be generated in a similar way to a standard search tree (decision tree) for solving a CSP, but some nodes are merged, creating a more compact representation; for certain classes of CSPs, the number of nodes in the resulting network will be a tiny fraction of the number of nodes in the corresponding search tree. A method is given for generating an SLDD that represents e.g., a particular instance of a semiring-based CSP; it is shown how this can be used to perform various computations of interest, such as computing solutions, determining the possible values of each variable, finding optimal solutions, counting solutions and random generation of solutions of a CSP. 1