Samiksha Jaiswal (Editor) I am a computer expert who loves a challenge. When I am not managing servers and fixing flaws, I write about it and other interesting things on various blogs.
A max-plus algebra is a semiring over the union of real numbers and ε=−∞, equipped with maximum and addition as the two binary operations. It can be used appropriately to determine marking times within a given Petri net and a vector filled with marking state at the beginning.
Let a and b be real scalars or ε. Then the operations maximum (implied by the max operator ⊕) and addition (plus operator ⊗) for these scalars are defined as
a⊕b=max(a,b)a⊗b=a+b
Watch: Max-operator ⊕ can easily be confused with the addition operation. Similar to the conventional algebra, all ⊗ - operations have a higher precedence than ⊕ - operations.
Matrix operations
Max-plus algebra can be used for matrix operands A, B likewise, where the size of both matrices is the same. To perform the A⊕B - operation, the elements of the resulting matrix at (row i, column j) have to be set up by the maximum operation of both corresponding elements of the matrices A and B:
[A⊕B]ij=[A]ij⊕[B]ij=max([A]ij,[B]ij)
The ⊗ - operation is similar to the algorithm of Matrix multiplication, however, every "+" calculation has to be substituted by an ⊕ - operation and every "⋅" calculation by a ⊗ - operation. More precisely, to perform the A⊗B - operation, where A is a m×p matrix and B is a p×n matrix, the elements of the resulting matrix at (row i, column j) are determined by matrices A (row i) and B (column j):
In order to handle marking times like −∞ which means "never before", the ε-element has been established by ε=−∞. According to the idea of infinity, the following equations can be found:
ε⊕a=aε⊗a=ε
To point the zero number out, the element e was defined by e=0. Therefore:
e⊗a=a.
Obviously, ε is the neutral element for the ⊕-operation, as e is for the ⊗-operation
Algebra properties
associativity:
commutativity :
distributivity:
zero element :
unit element:
idempotency of ⊕ :
Additional reading
Butkovič, Peter (2010), Max-linear Systems: Theory and Algorithms, Springer Monographs in Mathematics, Springer-Verlag, doi:10.1007/978-1-84996-299-5
