Max-plus algebra

From Wikipedia, the free encyclopedia

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$

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. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.