Methods and applications of (max,+) linear algebra
Methods and applications of (max,+) linear algebra
复制标题
DOI：
10.1007/bfb0023465
复制
发表时间：
1997-01-01
期刊：
影响因子：
--
通讯作者：
Plus, M
中科院分区：
文献类型：
--
作者：
Gaubert, S;Plus, M
自五十年代末以来，诸如“(max，+)半环”(R Boolean OR{-infinity}，max，+)或“热带半环”(N Boolean OR{+infinity}，min，+)之类的奇异半环已经被多次发明和再发明，涉及到不同的领域：制造系统的性能评估和离散事件系统理论；图论(路代数)和马尔可夫决策过程，哈密尔顿-雅可比理论；渐近分析(统计物理中的低温渐近，大偏差，WKB方法)；语言理论(具有多重性的自动机)。尽管有这种明显的丰富，但有一小部分常见的、非幼稚的基本结果和问题，通常在(max，+)社区之外是未知的，它们似乎在大多数应用程序中是有用的。这篇简短的综述文章的目的是给出我们认为是(max，+)结果的最小核心，并通过典型应用来说明这些结果，在语言理论、控制和运筹学(离散事件系统的性能评估，具有平均成本的马尔可夫决策过程的分析)的前沿。基本技巧包括：求解各种线性方程组，有时使用奇异的对称化和行列式技术；使用(max，+)Perron-Frobenius理论来研究(max，+)线性映射的动力学。我们指出了一些有待解决的问题和当前的发展。
Exotic semirings such as the "(max, +) semiring" (R boolean OR {-infinity}, max, +), or the "tropical semiring" (N boolean OR {+infinity}, min, +), have been invented and reinvented many times since the late fifties, in relation with various fields: performance evaluation of manufacturing systems and discrete event system 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 multiplicities).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 theory, 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, sometimes with exotic symmetrization and determinant techniques; using the (max, +) Perron-Frobenius theory to study the dynamics of (max, +) Linear maps. We point out some open problems and current developments.