# Max-plus algebra

A max-plus algebra is a semiring over the union of real numbers and ε = $-\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 ε$=-\infty$. According to the idea of infinity, the following equations can be found:

ε $\oplus$ a = a
ε $\otimes$ a = ε

To point the zero number out, the element e was defined by $e=0$. Therefore:

e $\otimes$ a = a

Obviously, ε is the neutral element for the $\oplus$ - operation, as e is for the $\otimes$ - operation

## Algebra properties

• associativity:
$(a \oplus b) \oplus c = a \oplus (b \oplus c)$
$(a\otimes b) \otimes c = a \otimes (b \otimes c)$
• commutativity :
$a \oplus b = b \oplus a$
$a \otimes b = b \otimes a$
• distributivity:
$(a \oplus b) \otimes c = a \otimes c \oplus b \otimes c$