Max-plus algebra

From Wikipedia, the free encyclopedia

A Max-plus algebra is an algebra over the real numbers 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.

1 Operators
- 1.1 Scalar Operations
- 1.2 Matrix Operations
2 Useful Enhancement Elements
3 Algebra Properties
4 See also
5 Internet Links

[edit] Operators

[edit] Scalar Operations

Let A and B be a scalar. Then the operations maximum (implied by the max operator $\oplus$ ) and addition (plus operator $\otimes$ ) for this scalars are defined as

$A \bigoplus B = max(A,B)$
$A \bigotimes B := A + B$

Watch: Max-operator $\oplus$ can easily be mixed up with the addition operation. All $\otimes$ - operations have a higher rank than $\oplus$ - operations.

[edit] Matrix Operations

Max-Plus algebra can be used for matrix operands M, N likewise. To perform the $R = M \oplus N$ - operation, the elements of the resulting matrix R (row i, column j) have to be set up by the maximum operation of both corresponding elements of the matrices M and N:
R_ij = M_ij $\oplus$ N_ij

The $\otimes$ - operation is similar to algorithm of Matrix multiplication, however, every " $\cdot$ " calculation has to be substituted by a $\otimes$ - operation, every "+" calculation by a $\oplus$ - operation.

[edit] 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 well as e is for the $\otimes$ - operation

[edit] 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

distributivity:

(A $\oplus$ B) $\otimes$ C = A $\otimes$ C $\oplus$ B $\otimes$ C

Note: B $\otimes$ A $\ne$ A $\otimes$ B (in general, similar to usual matrix algebra)