Semiring induced valuation algebras: Exact and approximate local computation algorithms
| dc.contributor.author | Kohlas, Juerg | |
| dc.contributor.author | Wilson, Nic | |
| dc.contributor.funder | Science Foundation Ireland | en |
| dc.date.accessioned | 2013-05-13T13:53:37Z | |
| dc.date.available | 2013-05-13T13:53:37Z | |
| dc.date.copyright | 2008 | |
| dc.date.issued | 2008-07 | |
| dc.date.updated | 2012-12-20T17:39:41Z | |
| dc.description.abstract | Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra. There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and non-classical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible. | en |
| dc.description.status | Peer reviewed | en |
| dc.description.version | Accepted Version | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.citation | Kohlas, J. and Wilson, N.; (2008) 'Semiring induced valuation algebras: Exact and approximate local computation algorithms'. Artificial Intelligence, 172 (11):1360-1399. doi:http://dx.doi.org/10.1016/j.artint.2008.03.003, | en |
| dc.identifier.doi | 10.1016/j.artint.2008.03.003 | |
| dc.identifier.endpage | 1399 | en |
| dc.identifier.issued | 11 | en |
| dc.identifier.journaltitle | Artificial Intelligence | en |
| dc.identifier.startpage | 1360 | en |
| dc.identifier.uri | https://hdl.handle.net/10468/1116 | |
| dc.identifier.volume | 172 | en |
| dc.language.iso | en | en |
| dc.publisher | Elsevier | en |
| dc.relation.project | info:eu-repo/grantAgreement/SFI/SFI Principal Investigator Programme (PI)/00/PI.1/C075/IE/Constraint Computation: Automation and Application/ | |
| dc.relation.project | info:eu-repo/grantAgreement/SFI/SFI Technology and Innovation Development Award (TIDA)/05/IN.1/I886 TIDA 09/IE/Costraint Baset Energy Cost Efficient Scheduling/ | |
| dc.relation.uri | http://www.sciencedirect.com/science/article/pii/S0004370208000428 | |
| dc.rights | © 2008 Elsevier B.V. NOTICE: this is the author’s version of a work that was accepted for publication in Artificial Intelligence. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Artificial Intelligence, Vol 172, Issue 11, 2008. DOI: http://dx.doi.org/10.1016/j.artint.2008.03.003, | en |
| dc.subject | Semirings | en |
| dc.subject | Local computation | en |
| dc.subject | Join tree decompositions | en |
| dc.subject | Soft constraints | en |
| dc.subject | Uncertainty | en |
| dc.subject | Valuation networks | en |
| dc.subject | Valuation algebras | en |
| dc.subject.lcsh | Computer science. | en |
| dc.title | Semiring induced valuation algebras: Exact and approximate local computation algorithms | en |
| dc.type | Article (peer-reviewed) | en |
