nLab
max-plus algebra

The max-plus algebra and min-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 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.

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

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.

Revised on September 4, 2011 11:47:33 by Toby Bartels (75.88.82.16)