List of Selby characters

2013-07-12T08:39:25Z

123.2.17.157: /* Inventions of Dr. Trifle */

A '''max-plus algebra''' is a [[semiring]] over the union of [[real number]]s and ε = <math>-\infty</math>, 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 <math> \oplus</math>) and addition ('''plus''' operator <math> \otimes</math>) for these scalars are defined as

: <math>a \oplus b = \max(a,b) </math>
: <math>a \otimes b = a + b</math>

'''Watch''': Max-operator <math>\oplus</math> can easily be confused with the addition operation. Similar to the conventional algebra, all <math>\otimes</math> - operations have a higher [[Order of operations|precedence]] than <math>\oplus</math> - 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''' <math>\oplus</math> '''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''':

: <math>[A \oplus B]_{ij} = [A]_{ij} \oplus [B]_{ij} = \max([A]_{ij} , [B]_{ij})</math>

The <math> \otimes</math> - operation is similar to the algorithm of [[Matrix multiplication]], however, every "+" calculation has to be substituted by an <math>\oplus</math> - operation and every "<math>\cdot</math>" calculation by a <math>\otimes</math> - operation. More precisely, to perform the '''A''' <math>\otimes</math> '''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):

: <math>[A \otimes B]_{ij} = \bigoplus_{k = 1}^p [A]_{ik} \otimes [B]_{kj} = \max([A]_{i1} + [B]_{1j}, \dots, [A]_{ip} + [B]_{pj})</math>

==Useful enhancement elements==
In order to handle marking times like <math>-\infty</math> which means "never before", the ε-element has been established by ε<math>=-\infty</math>. According to the idea of infinity, the following equations can be found:

: ε <math>\oplus</math> a = a
: ε <math>\otimes</math> a = ε
To point the zero number out, the element ''e'' was defined by <math>e=0</math>. Therefore:

: ''e'' <math>\otimes</math> ''a'' = ''a''

Obviously, ε is the neutral element for the <math>\oplus</math> - operation, as ''e'' is for the <math>\otimes</math> - operation

==Algebra properties==
*associativity:

:: <math>(a \oplus b) \oplus c = a \oplus (b \oplus c) </math>

:: <math>(a\otimes b) \otimes c = a \otimes (b \otimes c) </math>

*commutativity :

:: <math>a \oplus b = b \oplus a </math>

:: <math>a \otimes b = b \otimes a </math>

*distributivity:

:: <math> (a \oplus b) \otimes c = a \otimes c \oplus b \otimes c </math>

==See also==
* [[Tropical geometry]]

==Additional reading==
*{{citation|title=Max-linear Systems: Theory and Algorithms|first=Peter|last=Butkovič|series=Springer Monographs in Mathematics|doi=10.1007/978-1-84996-299-5|publisher=Springer-Verlag|year=2010}}

==External links==
*http://maxplus.org
*http://amadeus.inria.fr/gaubert/maxplus.html

[[Category:Algebras]]

[[fr:Algèbre max-plus]]

formulasearchengine - User contributions [en]

List of Selby characters