Semiring analogies
Sunday, October 9th, 2005Sigfpe has been posting on his blog about one of my minor obsessions, semirings. A semiring is a ring without subtraction. There are lots of semirings that arise in both pure and applied mathematics. Here are some examples that show just how common they are:
- Any collection of sets closed under union and intersection form a semiring, with union as addition and intersection as multiplication (or vice versa).
- Regular languages form a semiring. The sum of two regular languages is the union, while the product is juxtaposition.
- The reals with positive infinity added form a semiring where the “sum“ of two numbers is the minimum, and the “product“ is addition. (Including positive infinity is not strictly necessary, but it serves as a “zero“ for the min operation). This known as the min-plus semiring.
The last example has an interesting extra property: you can take infinite “sums“ by taking the infimum of an infinite set of elements. You can set up an extended analogy between the reals with usual arithmetic operations and the min-plus semiring. In this analogy, integration becomes optimization. You can even extend the analogy as far as the Fourier transform. The min-plus analogue of the Fourier transform is the Legendre transform that arises in classical mechanics. Sigfpe explains the analogy here.
He has also posted about an application of semirings to understanding the game Tetris.