Max-plus algebra

A max-plus algebra is an algebra over the real numbers 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 scalars. Then the operations maximum (implied by the max operator $\oplus$) and addition (plus operator $\otimes$) for this 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. All $\otimes$ - operations have a higher precedence than $\oplus$ - operations.

Matrix operations

Max-Plus algebra can be used for matrix operands M, N likewise. To perform the $R = M \oplus N$ - 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 and N:

R_ij = M_ij $\oplus$ N_ij

The $\otimes$ - operation is similar to algorithm of Matrix multiplication, however, every "+" calculation has to be substituted by a $\oplus$ - operation, every "$\cdot$" calculation by a $\otimes$ - operation.

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 well 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$

• distributivity:

$(A \oplus B) \otimes C = A \otimes C \oplus B \otimes C$

Note: In general, A $\otimes$ B = B $\otimes$ A does not hold, for example in the case of matrix operations.

See also

• Tropical geometry

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

• http://maxplus.org
• http://amadeus.inria.fr/gaubert/maxplus.html

This algebra-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Algebras Algebra stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем написать реферат Henry Metz Polish 2nd Legions Infantry Division Look at other dictionaries: Max-Plus-Algebra — Eine Max Plus Agebra ist ein mathematisches Objekt, das vergleichbar ist mit einer Algebra über den reellen Zahlen, wobei jedoch die Körper Operationen ersetzt werden: die Addition durch das Bilden des Maximums, die Multiplikation durch die… …   Deutsch Wikipedia Algebra over a field — This article is about a particular kind of vector space. For other uses of the term algebra , see algebra (disambiguation). In mathematics, an algebra over a field is a vector space equipped with a bilinear vector product. That is to say, it is… …   Wikipedia Canonical form (Boolean algebra) — In Boolean algebra, any Boolean function can be expressed in a canonical form using the dual concepts of minterms and maxterms. Minterms are called products because they are the logical AND of a set of variables, and maxterms are called sums… …   Wikipedia Ordinal optimization — In mathematical optimization, ordinal optimization is the maximization of functions taking values in a partially ordered set ( poset ). Ordinal optimization has applications in the theory of queuing networks. Contents 1 Mathematical foundations 1 …   Wikipedia Network calculus — is a theoretical framework for analysing performance guarantees in computer networks. As traffic flows through a network it is subject to constraints imposed by the system components, for example: link capacity traffic shapers (leaky buckets)… …   Wikipedia List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia Tropical geometry — is a relatively new area in mathematics, which might loosely be described as a piece wise linear or skeletonized version of algebraic geometry. Its leading ideas had appeared in different guises in previous works of George M. Bergman and of… …   Wikipedia Semifield — In mathematics, a semifield is an algebraic structure with two binary operations, addition and multiplication, which is similar to the field, but with some axioms relaxed. There are at least two conflicting conventions of what constitutes a… …   Wikipedia Mathematical analysis — Mathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and… …   Wikipedia List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”