CHAPTER 6
VALUATION ALGEBRAS FOR PATH PROBLEMS
Together with semiring constraint systems introduced in Chapter 5, the solution of path problems in graphs surely ranks among the most popular and important application fields of semiring theory in computer science. In fact, the history of research in path problems strongly resembles that of valuation algebras and local computation in its search for genericity and generality. In the beginning, people studied specific path problems which quickly brought out a large number of seemingly different algorithms. Based on this research, it was then observed that path problems often provide a common algebraic structure. This gave birth of an abstract framework called algebraic path problem which unifies the formerly isolated tasks. Typical instances of this framework include the computation of shortest distances, maximum capacities or reliabilities, but also other problems that are not directly related to graphs such as partial differentiation or the determination of the language accepted by a finite automaton. This common algebraic viewpoint initiated the development of generic procedures for the solution of the algebraic path problem, similar to our strategy of defining generic local computation architectures for the solution of inference problems. Since the algebraic path problem is not limited to graph related applications, its definition is based on a matrix of semiring values instead. We will show in this chapter that depending on the ...
