Decision diagrams for the computation of semiring valuations
| dc.contributor.author | Wilson, Nic | |
| dc.contributor.funder | Science Foundation Ireland | en |
| dc.date.accessioned | 2020-11-17T16:33:26Z | |
| dc.date.available | 2020-11-17T16:33:26Z | |
| dc.date.issued | 2005-07 | |
| dc.date.updated | 2020-11-04T13:29:30Z | |
| 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.description.status | Peer reviewed | en |
| dc.description.version | Accepted Version | en |
| dc.format.mimetype | application/pdf | en |
| 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.endpage | 336 | en |
| dc.identifier.startpage | 331 | en |
| dc.identifier.uri | https://hdl.handle.net/10468/10768 | |
| dc.language.iso | en | en |
| dc.publisher | International Joint Conferences on Artificial Intelligence (ICJAI) | 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 |
| dc.relation.uri | https://www.ijcai.org/Proceedings/2005 | |
| 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 |
