A max-plus algebra
is an algebra
In mathematics, an algebra over a field is a vector space equipped with a bilinear vector product. That is to say, it isan algebraic structure consisting of a vector space together with an operation, usually called multiplication, that combines any two vectors to form a third vector; to qualify as...
over the real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s with maximum and addition as the two binary operations.
It can be used appropriately to determine marking times within a given Petri net
A Petri net is one of several mathematical modeling languages for the description of distributed systems. A Petri net is a directed bipartite graph, in which the nodes represent transitions and places...
and a vector filled with marking state at the beginning.
be scalars. Then the operations maximum (implied by the max
) and addition (plus
) for this scalars are defined as
can easily be confused with the addition operation. All
- operations have a higher precedence
In mathematics and computer programming, the order of operations is a rule used to clarify unambiguously which procedures should be performed first in a given mathematical expression....
Max-Plus algebra can be used for matrix operands M
likewise. To perform the
- 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
- Rij = Mij Nij
- operation is similar to algorithm of Matrix multiplication
In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the...
, however, every "+" calculation has to be substituted by a
- operation, every "
" calculation by a
Useful enhancement elements
In order to handle marking times like
which means "never before", the ε-element has been established by ε
. According to the idea of infinity, the following equations can be found:
- ε A = A
- ε A = ε
To point the zero number out, the element e
was defined by
- e A = A
Obviously, ε is the neutral element for the
- operation as well as e
is for the
Note: In general, A
B = B
A does not hold, for example in the case of matrix operations.