Decision diagrams for the computation of semiring valuations

Thumbnail Image
SLDDIJCAI.pdf(88.85 KB)
Accepted version
Wilson, Nic
Journal Title
Journal ISSN
Volume Title
International Joint Conferences on Artificial Intelligence (ICJAI)
Published Version
Research Projects
Organizational Units
Journal Issue
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.
Link to publisher’s version
© 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