# Max-plus algebra

A max-plus algebra is a semiring over the union of real numbers and ${\displaystyle \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 ${\displaystyle \oplus }$) and addition (plus operator ${\displaystyle \otimes }$) for these scalars are defined as

${\displaystyle a\oplus b=\max(a,b)}$
${\displaystyle a\otimes b=a+b}$

Watch: Max-operator ${\displaystyle \oplus }$ can easily be confused with the addition operation. Similar to the conventional algebra, all ${\displaystyle \otimes }$ - operations have a higher precedence than ${\displaystyle \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 ${\displaystyle \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:

${\displaystyle [A\oplus B]_{ij}=[A]_{ij}\oplus [B]_{ij}=\max([A]_{ij},[B]_{ij})}$

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

${\displaystyle [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 ${\displaystyle -\infty }$ which means "never before", the ε-element has been established by ${\displaystyle \varepsilon =-\infty }$. According to the idea of infinity, the following equations can be found:

${\displaystyle \varepsilon \oplus a=a}$
${\displaystyle \varepsilon \otimes a=\varepsilon }$

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

${\displaystyle e\otimes a=a.\,}$

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

## Algebra properties

• associativity:
${\displaystyle (a\oplus b)\oplus c=a\oplus (b\oplus c)}$
${\displaystyle (a\otimes b)\otimes c=a\otimes (b\otimes c)}$
• commutativity :
${\displaystyle a\oplus b=b\oplus a}$
${\displaystyle a\otimes b=b\otimes a}$
• distributivity:
${\displaystyle (a\oplus b)\otimes c=a\otimes c\oplus b\otimes c}$
• zero element :
${\displaystyle a\oplus \varepsilon =a}$
• unit element:
${\displaystyle a\otimes e=a}$
• idempotency of ${\displaystyle \oplus }$ :
${\displaystyle a\oplus a=a}$