We have recently seen quite a resurgence of interest in semirings and related algebraic structures. While mathematicians have known about these structures for a long time, as with monoids, they have not received much attention. They do not have enough structure to be interesting, at least from the point of view of proving powerful theorems. Computer scientists are not looking for powerful theorems, but they do value ubiquity, polymorphism, and reuse, issues where monoids shine, as do semirings, somewhat belatedly.

While a textbook-length treatise on such matters has already been written [1], this whole area is still relatively unknown, even among computer scientists, which explains the publication of papers such as this one, as well as a recent pearl on the subject [2], and a variety of blog posts. They are all interesting, especially for their contributions to the unification of a great many algorithms. This paper and Gondran and Minoux’s book [1] both present this most clearly.

But this paper does more: it also systematically shows how to prove the correctness of classical algorithms, using very general (and unified) principles. This is followed by a nice overview of a number of applications.

While perhaps not the gentlest introduction to the topic, the paper is well written and mathematically rigorous. I believe it would be accessible to a computer scientist curious about how these various classical algorithms can be unified.