Decision diagrams for the computation of semiring valuations

Show simple item record Wilson, Nic 2020-11-17T16:33:26Z 2020-11-17T16:33:26Z 2005-07
dc.identifier.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. en
dc.identifier.startpage 331 en
dc.identifier.endpage 336 en
dc.description.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. en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher International Joint Conferences on Artificial Intelligence (ICJAI) en
dc.rights © 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 en
dc.subject Computation en
dc.subject Semiring-labelled decision diagrams (SLDDs) en
dc.subject Decision diagrams en
dc.title Decision diagrams for the computation of semiring valuations en
dc.type Conference item en
dc.internal.authorcontactother Nic Wilson, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: en
dc.internal.availability Full text available en 2020-11-04T13:29:30Z
dc.description.version Accepted Version en
dc.internal.rssid 52485600
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.internal.copyrightchecked No
dc.internal.licenseacceptance Yes en
dc.internal.IRISemailaddress en
dc.relation.project info:eu-repo/grantAgreement/SFI/SFI Principal Investigator Programme (PI)/00/PI.1/C075/IE/Constraint Computation: Automation and Application/ en

Files in this item

This item appears in the following Collection(s)

Show simple item record

This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement