下载
Methods and Applications of (max,+) Linear Algebra
St´ephane Gaubert and Max Plus
?
INRIA, Domaine de Voluceau, BP105, 78153 Le Chesnay Cedex, France.
e-mail: Stephane.Gaubert@inria.fr
Abstract. Exotic semirings such as the “(max, +) semiring” (
R ∪
{−∞}, max, +), or the “tropical semiring” (
N ∪{+∞}, min, +), have been
invented and reinvented many times since the late fifties, in relation with various
fields:performanceevaluationofmanufacturingsystemsanddiscreteeventsystem
theory; graph theory (path algebra) and Markov decision processes, Hamilton-
Jacobi theory; asymptotic analysis (low temperature asymptotics in statistical
physics, large deviations, WKB method); language theory (automata with multi-
plicities).
Despite this apparent profusion, there is a small set of common, non-naive, basic
results and problems, in general not known outside the (max, +) community,
which seem to be useful in most applications. The aim of this short survey paper
is to present what we believe to be the minimal core of (max, +) results, and
to illustrate these results by typical applications, at the frontier of language the-
ory, control, and operations research (performance evaluation of discrete event
systems, analysis of Markov decision processes with average cost).
Basic techniques include: solving all kinds of systems of linear equations, some-
timeswithexoticsymmetrization and determinant techniques; using the(max, +)
Perron-Frobeniustheorytostudythedynamicsof(max, +) linearmaps.We point
out some open problems and current developments.
1 Introduction: the (max, +) and tropical semirings
The “max-algebra” or “(max, +) semiring” R
max
, is the set R ∪{−∞}, equipped with
max as addition, and + as multiplication. It is traditional to use the notation ⊕ for
max (2 ⊕ 3=3), and ⊗ for +(1⊗1=2). We denote
1
by 0 the zero element for
⊕ (such that 0 ⊕ a = a, here 0 = −∞) and by 1 the unit element for ⊗ (such that
1 ⊗a = a ⊗ 1 = a, here 1 =0). This structure satisfies all the semiring axioms, i.e. ⊕
is associative, commutative, with zero element, ⊗ is associative, has a unit, distributes
over ⊕, and zero is absorbing (all the ring axioms are satisfied, except that ⊕ need not
be a group law). This semiring is commutative (a ⊗b = b ⊗a), idempotent (a ⊕a = a),
?
Max Plus is a collective name for a working group on (, +) algebra, at INRIA Rocquencourt,
comprising currently: Marianne Akian, Guy Cohen, S.G., Jean-Pierre Quadrat and Michel Viot.
1
The notation for the zero and unit is one of the disputed questions of the community. The
symbols ε for zero, and e for the unit, often used in the literature, are very distinctive and well
suited to handwritten computations. But it is difficult to renounce to the traditional use of ε
in Analysis. The notation 0, 1 used by the Idempotent Analysis school has the advantage of
making formulæ closer to their usual analogues.
14th Symposium on Theoretical Aspects of Computer Science, Hansestadt Lübeck, Germany,
Feb. 27–March 1, 1997 (to appear in Springer Lecture Notes in Computer Science)
