Max-plus algebra

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

Scalar operations[edit]

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

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

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

  • 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

See also[edit]

Additional reading[edit]

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