Decision diagrams for the computation of semiring valuations
International Joint Conferences on Artificial Intelligence (ICJAI)
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.
Computation , Semiring-labelled decision diagrams (SLDDs) , Decision diagrams
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.
© August 1, 2005 International Joint Conferences on Artificial Intelligence. All rights reserved. This publication, or parts thereof, may not be reproduced in any form without permission