Max-plus algebra

A max-plus algebra is a semiring over the union of real numbers and $\varepsilon = -\infty$ , 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.

Operators

Scalar operations

Let a and b be real scalars or ε. Then the operations maximum (implied by the max operator $\oplus$ ) and addition (plus operator $\otimes$ ) for these scalars are defined as

a \oplus b = \max(a,b)

a \otimes b = a + b

Watch: Max-operator $\oplus$ can easily be confused with the addition operation. Similar to the conventional algebra, all $\otimes$ - operations have a higher precedence than $\oplus$ - 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 $\oplus$ 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 \oplus B]_{ij} = [A]_{ij} \oplus [B]_{ij} = \max([A]_{ij} , [B]_{ij})

The $\otimes$ - operation is similar to the algorithm of Matrix multiplication, however, every "+" calculation has to be substituted by an $\oplus$ - operation and every " $\cdot$ " calculation by a $\otimes$ - operation. More precisely, to perform the A $\otimes$ 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):

[A \otimes B]_{ij} = \bigoplus_{k = 1}^p ( [A]_{ik} \otimes [B]_{kj} ) = \max([A]_{i1} + [B]_{1j}, \dots, [A]_{ip} + [B]_{pj})

Useful enhancement elements

In order to handle marking times like $-\infty$ which means "never before", the ε-element has been established by $\varepsilon=-\infty$ . According to the idea of infinity, the following equations can be found: