Idempotency (Publications of the Newton Institute, Series Number 11)

Certain nonlinear optimization problems arise in such areas as the theory of computation, pure and applied probability, and mathematical physics. These problems can be solved through linear methods, providing the usual number system is replaced with one that satisfies the idempotent law. Only recently has a systematic study of idempotency analysis emerged, triggered in part by a workshop organized by Hewlett-Packard's Basic Research Institute in the Mathematical Sciences (BRIMS), which brought together for the first time many leading researchers in the area. This volume, a record of that workshop, includes a variety of contributions, a broad introduction to idempotency, written especially for the book, and a bibliography of the subject. It is the most up-to-date survey currently available of research in this developing area of mathematics; the articles cover both practical and more theoretical considerations, making it essential reading for all workers in the area. Cover......Page 1 Title......Page 4 Copyright......Page 5 Contents......Page 6 Foreword......Page 8 Preface......Page 10 List of Participants......Page 12 An Introduction to Idempotency......Page 14 Tropical semirings......Page 63 Some automata-theoretic aspects of min-max-plus semirings......Page 83 The finite power property for rational sets of a free group......Page 93 The topological approach to the limitedness problem on distance automata......Page 101 Types and dynamics in partially additive categories......Page 125 Task resource models and (max, +) automata......Page 146 Algebraic system analysis of timed Petri nets......Page 158 Ergodic theorems for stochastic operators and discrete event networks.......Page 184 Computational issues in recursive stochastic systems......Page 222 Periodic points of nonexpansive maps......Page 244 A system-theoretic approach for discrete-event control of manufacturing systems......Page 255 Idempotent structures in the supervisory control of discrete event systems......Page 275 Maxpolynomials and discrete-event dynamic systems......Page 295 The Stochastic HJB equation and WKB method......Page 298 The Lagrange problem from the point of view of idempotent analysis......Page 316 A new differential equation for the dynamics of the Pareto sets......Page 335 Duality between probability and optimization......Page 344 Maslov optimization theory: topological aspects......Page 367 Random particle methods in (max,+) optimization problems......Page 396 The geometry of finite dimensional pseudomodules......Page 405 A general linear max-plus solution technique......Page 419 Axiomatics of thermodynamics and idempotent analysis......Page 429 The correspondence principle for idempotent calculus and some computer applications......Page 433 Certain nonlinear optimization problems arising in such disparate areas as the theory of computation, pure and applied probability and mathematical physics, can be solved by linear methods, provided one replaces the usual number system with one in which addition satisfies the idempotent law. This systematic study of the subject has emerged, triggered in part by a workshop organized by Hewlett-Packard's Basic Research Institute in the Mathematical Sciences (BRIMS), which brought together many leading researchers in the area. This volume is a record of that workshop, but it also includes other invited contributions, a broad Introduction to Idempotency, written specially for the book, and a bibliography of the subject. In sum, the articles cover both practical and more theoretical considerations, making it essential reading for all workers in the area