max-plus algebra

The max-plus algebra and min-plus algebra


The max-plus algebra, or tropical semiring, is the rig based on the set of real numbers extended by -\infty (the upper reals), with addition xy=max(x,y)x \oplus y = max(x,y) and multiplication xy=x+yx \otimes y = x + y. Similarly, the min-plus algebra, or rig of costs, is the rig based on the set of real numbers extended by \infty (the lower reals), with addition xy=min(x,y)x \oplus y = min(x,y) and multiplication xy=x+yx \otimes y = x + y. The two rigs are isomorphic, with an isomorphism (either way) given by xxx \mapsto -x; the difference is just a matter of the desired perspective.


The max-plus algebra is an idempotent semiring and dioid that is used in the modelling of timed systems. Typically in a simple example, the completion time of a production system will be given by a system of equations that have ‘max’ occurring in them. (The next process in a system cannot start until all its component parts have been themselves completed.) The use of the max-plus notation completely linearises many systems.

The min-plus algebra may be used to draw an analogy between the use of action? in classical vs quantum systems. While the latter involves a sum of a multiplicative action over classical trajectories?, the former involves a minimisation of an additive action over classical trajectories. There is a similar analogy between statics? and statistical mechanics.



There are several research groups, world wide, with research in this area and with good websites, including simulation, and calculational, tools. One way into the network of these sites is here.

Last revised on September 4, 2011 at 11:47:33. See the history of this page for a list of all contributions to it.