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:

\varepsilon \oplus a=a

\varepsilon \otimes a=\varepsilon

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

zero element :

a \oplus \varepsilon = a

unit element:

a \otimes e = a

idempotency of $\oplus$ :

a \oplus a = a

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

External links

This article is issued from Wikipedia - version of the 4/2/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.