Semiring induced valuation algebras: Exact and approximate local computation algorithms

Show simple item record

dc.contributor.author Kohlas, Juerg
dc.contributor.author Wilson, Nic
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.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.volume 172 en
dc.identifier.issued 11 en
dc.identifier.startpage 1360 en
dc.identifier.endpage 1399 en
dc.identifier.uri http://hdl.handle.net/10468/1116
dc.identifier.doi 10.1016/j.artint.2008.03.003
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.sponsorship Science Foundation Ireland (00/PI.1/C075); Science Foundation Ireland (05/IN/I886) en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Elsevier en
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
dc.internal.authorurl http://research.ucc.ie/profiles/D005/nwilson en
dc.internal.authorcontactother Nic Wilson, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: n.wilson@4c.ucc.ie en
dc.internal.availability Full text available en
dc.date.updated 2012-12-20T17:39:41Z
dc.description.version Accepted Version en
dc.internal.rssid 51139447
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.identifier.journaltitle Artificial Intelligence en
dc.internal.copyrightchecked No. CORA - ROMEO en
dc.internal.licenseacceptance Yes en
dc.internal.IRISemailaddress n.wilson@ucc.ie 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