Semiring Valuation Algebras
Marc Pouly, Jürg Kohlas · 2011
A generic construction identifies a family of valuation algebra instances that share a common structure. This chapter introduced two generic constructions related to semirings. Semiring valuations are mappings from configurations to values of a commutative semiring. This allows directly to assimilate the many important formalisms used in soft constraint reasoning into the valuation algebra framework and to immediately conclude that they all qualify for the application of local computation. A closer inspection of semiring valuation algebras in general identified the sufficient properties of a semiring to induce valuation algebras with neutral and null elements or with a division and scaling operator. This again discharges us from analysing each formalism individually. The second family of valuation algebras studies in this chapter are set-based semiring valuations, obtained from mapping sets of configurations to semiring values. Its best known member is the formalism of set potentials. Controlled Vocabulary Terms algebra; computational geometry