nLab max-plus algebra

Definitions

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 $x \oplus y = max(x,y)$ and multiplication $x \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 $x \oplus y = min(x,y)$ and multiplication $x \otimes y = x + y$. The two rigs are isomorphic, with an isomorphism (either way) given by $x \mapsto -x$; the difference is just a matter of the desired perspective.

Applications

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.

References

• Stéphane Gaubert, Introduction aux Systèmes Dynamiques à Événements Discrets

• Stéphane Gaubert, Methods and Applications of $(max,+)$ Linear Algebra Report 3088, January 1997, INRIA.

• John Baez & David Corfield, Changing the rig

• Jean-Pierre Quadrat, Max-Plus Algebra and Applications to System Theory and Optimal Control, Proccedings of the International Congress of Mathematicians , Zurich 1994, Birkhauser , 1995.

Resources

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.