CHAPTER 5

SEMIRING VALUATION ALGEBRAS

The mathematical framework of valuation algebras introduced in Chapter 1 provides sufficient structure for the application of generic local computation methods. In the process, the numerous advantages of such a general framework became clear, and we have seen for ourselves that different formalisms are unified under this common perspective. As a fundamental requirement for this generality, we did not assume any further knowledge about the structure of valuations. They have only been considered as mathematical objects that possess a domain and that can further be combined and projected according to certain axioms. For certain applications, however, it is useful to have additional knowledge about the structure of valuations. This amounts to the identification of families of valuation algebra instances which share some common structure. A first example of such a family of valuation algebras grows out of the obvious similar structure of indicator functions and arithmetic potentials introduced as Instances 1.1 and 1.3. On the one hand, both instances are obtained by assigning values to tuples out of a finite set of tuples, but on the other hand, they differ in their definitions of combination and projection. Yet, there is a common ground between them. We will learn in this chapter that both examples belong to a family of instances, called semiring valuation algebras. A commutative semiring is by itself a fundamental algebraic structure that comprises ...

Get Generic Inference: A Unifying Theory for Automated Reasoning now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.