Decision diagrams for the computation of semiring valuations

Wilson, Nic

Decision diagrams for the computation of semiring valuations

Files

SLDDIJCAI.pdf(88.85 KB)

Accepted version

Date

2005-07

Authors

Wilson, Nic

Publisher

International Joint Conferences on Artificial Intelligence (ICJAI)

Abstract

This paper describes a new approach to computation in a semiring-based 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). These 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 solving a semiring-based CSP, finding optimal solutions, determining the possible values of each variable and counting solutions of a CSP.

Keywords

Computation , Semiring-labelled decision diagrams (SLDDs) , Decision diagrams

Citation

Wilson, N. (2005) 'Decision Diagrams for the Computation of Semiring Valuations', IJCAI'05: Proceedings of the 19th International Joint Conference on Artificial intelligence, Edinburgh, Scotland, 30 July - 05 August, pp. 331-336.