article

From max-plus algebra to nonexpansive mappings: a nonlinear theory for discrete event systems

Author:

Jeremy GunawardenaAuthors Info & Claims

Theoretical Computer Science, Volume 293, Issue 1

Pages 141 - 167

https://doi.org/10.1016/S0304-3975(02)00235-9

Published: 03 February 2003 Publication History

Abstract

Discrete event systems provide a useful abstraction for modelling a wide variety of systems: digital circuits, communication networks, manufacturing plants, etc. Their dynamics--stability, equilibrium states, cyclical behaviour, asymptotic average delays--are of vital importance to system designers. However, in marked contrast to continuous dynamical systems, there has been little systematic mathematical theory that designers can draw upon. In this paper, we survey the development of such a theory, based on the dynamics of maps which are nonexpansive in the l^∞ norm. This has its origins in linear algebra over the max-plus semiring but extends to a nonlinear theory that encompasses a variety of problems arising in other mathematical disciplines. We concentrate on the mathematical aspects and set out several open problems.

References

[1]

{1} N. Aronszajn, P. Panitchpakdi, Extension of uniformly continuous transformations and hyperconvex metric spaces, Pacific J. Math. 6 (1956) 405-439.

[2]

{2} F. Baccelli, G. Cohen, G.J. Olsder, J.-P. Quadrat, Synchronization and Linearity, Wiley Series in Probability and Mathematical Statistics, Wiley, New York, 1992.

[3]

{3} F. Baccelli, J. Mairesse, Ergodic theorems for stochastic operators and discrete event systems, in: J. Gunawardena (Ed.), Idempotency, Publications of the Isaac Newton Institute, Cambridge University Press, Cambridge, 1998.

[4]

{4} W. Backes, The structure of longest paths in periodic graphs, Ph.D. Thesis, Universität des Saarlandes, 1994.

[5]

{5} A. Berman, R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Classics in Applied Mathematics, SIAM, Philadelphia, PA, 1994.

[6]

{6} D.P. Bertsekas, S.E. Shreve, Stochastic Optimal Control: the Discrete Time Case, Athena Scientific, 1996.

Digital Library

[7]

{7} T. Bewley, E. Kohlberg, The asymptotic theory of stochastic games, Math. Oper. Res. 1 (3) (1976) 197-208.

Digital Library

[8]

{8} T. Bewley, E. Kohlberg, On stochastic games with stationary optimal strategies, Math. Oper. Res. 3 (2) (1978) 104-125.

Digital Library

[9]

{9} A. Blokhuis, H.A. Wilbrink, Alternative proof of Sine's theorem on the size of a regular polygon in Rn with the l∞ metric, Discrete Comput. Geometry 7 (1992) 433-434.

Digital Library

[10]

{10} R.F. Brown, A Topological Introduction to Nonlinear Analysis, Birkhäuser, Basel, 1993.

[11]

{11} E. Burmeister, R. Dobell, Mathematical Theories of Economic Growth, Macmillan, New York, 1970.

[12]

{12} S.M. Burns, Performance analysis and optimization of asynchronous circuits, Ph.D. Thesis, California Institute of Technology, 1990.

[13]

{13} B.A. Carré, An algebra for network routing problems, J. Inst. Math. Appl. 7 (1971) 273-294.

[14]

{14} J. Cochet-Terrasson, S. Gaubert, J. Gunawardena, A constructive fixed point theorem for min-max functions, Discrete Event Dynamic Systems 14 (4) (1999) 407-433.

[15]

{15} G. Cohen, D. Dubois, J.-P. Quadrat, M. Viot, A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing, IEEE Trans. Automat. Control 30 (3) (1985) 210-220.

[16]

{16} M.G. Crandall, L. Tartar, Some relations between nonexpansive and order preserving maps, Proc. AMS 78 (3) (1980) 385-390.

[17]

{17} R.A. Cuninghame-Green, Describing industrial processes with interference and approximating their steady-state behaviour, Oper. Res. Quart. 13 (1) (1962) 95-100.

[18]

{18} R.A. Cuninghame-Green, Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, vol. 166, Springer, Berlin, 1979.

[19]

{19} N.G. de Bruijn, Asymptotic Methods in Analysis, Dover, New York, 1981.

[20]

{20} S. Even, S. Rajsbaum, Unison, canon and sluggish clocks in networks controlled by a synchronizer, Math. Systems Theory 28 (1995) 421-435.

[21]

{21} G.L. Ferrari, U. Montanari, Dynamic matrices and the cost analysis of concurrent processes, in: S.A. Vangalur, M. Nivat (Eds.), Algebraic Methodology and Software Technology, Proceedings, Lecture Notes in Computer Science, volume 936, Springer-Verlag 1995.

Digital Library

[22]

{22} S. Gaubert, Théorie des Systèmes Linéaires dans les Dioides, Ph.D. Thesis, L' École Nationale Supérieure des Mines de Paris, 1992.

[23]

{23} S. Gaubert, J. Gunawardena, A non-linear hierarchy for discrete event dynamical systems, Proc. WODES'98, IEE, Cagliari, Italy, August 1998.

[24]

{24} S. Gaubert, J. Gunawardena, The duality theorem for min-max functions, C. R. Acad. Sci. 326 (1998) 43-48.

[25]

{25} S. Gaubert, J. Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions, math.FA0105091, submitted for publication.

[26]

{26} P. Glasserman, D.D. Yao, Monotone Structure in Discrete Event Systems, Wiley Series in Probability and Mathematical Statistics, Wiley, New York, 1994.

Digital Library

[27]

{27} K. Goebel, W.A. Kirk, Topics in Metric Fixed Point Theory, Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1990.

[28]

{28} M. Gondran, M. Minoux, Graphs and Algorithms, Wiley-Interscience Series in Discrete Mathematics, Wiley, New York, 1984.

Digital Library

[29]

{29} J. Gunawardena, Timing analysis of digital circuits and the theory of min-max functions, in: Digest of Technical Papers of the ACM International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, ACM, New York, 1993.

[30]

{30} J. Gunawardena, Min-max functions, Discrete Event Dynamic Systems 4 (1994) 377-406.

[31]

{31} J. Gunawardena (Ed.), Idempotency, Publications of the Isaac Newton Institute, Cambridge University Press, Cambridge, 1998.

[32]

{32} J. Gunawardena, An introduction to idempotency, in: J. Gunawardena (Ed.), Idempotency, Publications of the Isaac Newton Institute, Cambridge University Press, Cambridge, 1998.

[33]

{33} J. Gunawardena, M. Keane, On the existence of cycle times for some nonexpansive maps, Technical Report HPL-BRIMS-95-003, Hewlett-Packard Labs, 1995.

[34]

{34} H. Hulgaard, S.M. Burns, T. Amon, G. Borriello, An algorithm for exact bounds on the time separation of events in concurrent systems, IEEE Trans. Comput. 44 (1995) 1306-1317.

Digital Library

[35]

{35} E. Katirtzoglou, The cycle time vector of D-A-D functions, Linear Algebra Appl. 293 (1999) 133-144.

[36]

{36} D.A. Klain, G.-C. Rota, Introduction to Geometric Probability, Lezioni Lincee, Cambridge University Press, Cambridge, 1997.

[37]

{37} E. Kohlberg, Invariant half-lines of nonexpansive piecewise-linear transformations, Math. Oper. Res. 5 (3) (1980) 366-372.

Digital Library

[38]

{38} E. Kohlberg, A. Neyman, Asymptotic behaviour of nonexpansive mappings in normed linear spaces, Israel I. Math. 48 (4) (1981) 269-275.

[39]

{39} V.N. Kolokoltsov, On linear, additive and homogeneous operators in idempotent analysis, in: V.P. Maslov, S.N. Sambovski (Eds.), Idempotent Analysis, Advances in Soviet Mathematics, vol. 13, American Mathematical Society, Providence, RI, 1992.

[40]

{40} R.N. Lyons, R.D. Nussbaum, On transitive and commutative finite groups of isometries, in: K.-K. Tan (Ed.), Fixed Point Theory and Applications, World Scientific, Singapore, 1992, pp. 189-229.

[41]

{41} Max-Plus Working Group, Max-plus algebra and applications to system theory and optimal control, in: Proc, Internat. Congr. Mathematicians, Zürich, 1994, Birkhäuser, Basel, 1995.

[42]

{42} M. Menon, H. Schneider, The spectrum of an operator associated with a matrix, Linear Algebra Appl. 2 (1969) 321-334.

[43]

{43} H. Minc, Nonnegative Matrices, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, New York, 1988.

[44]

{44} R.D. Nussbaum, Hilbert's projective metric and iterated nonlinear maps, Mem. AMS 75 (391) (1988).

[45]

{45} R.D. Nussbaum, Iterated nonlinear maps and Hilbert's projective metric, II, Mem. AMS 79 (401) (1989).

[46]

{46} R.D. Nussbaum, Omega limit sets of nonexpansive maps: finiteness and cardinality estimates, Differential Integral Equations 3 (1990) 523-540.

[47]

{47} R.D. Nussbaum, Periodic points of nonexpansive maps, in: J. Gunawardena (Ed.), Idempotency, Publications of the Isaac Newton Institute, Cambridge University Press, Cambridge, 1998.

[48]

{48} G.J. Olsder, Eigenvalues of dynamic max-min systems, Discrete Event Dynamic Systems 1 (1991) 177-207.

[49]

{49} S. Rajsbaum, M. Sidi, On the performance of synchronized programs in distributed networks with random processing times and transmission delays, IEEE Trans. Parallel Distributed Systems 5 (1994) 939-950.

Digital Library

[50]

{50} C.V. Ramamoorthy, G.S. Ho, Performance evaluation of asynchronous concurrent systems using Petri nets, IEEE Trans. Software Engng. SE-6 (5) (1980) 440-449.

Digital Library

[51]

{51} R. Reiter, Scheduling parallel computations, J. ACM 15 (4) (1968) 590-599.

Digital Library

[52]

{52} U.G. Rothblum, P. Whittle, Growth optimality for branching Markov decision chains, Math. Oper. Res. 7 (1982) 582-601.

Digital Library

[53]

{53} C. Sabot, Existence and uniqueness of diffusions on finitely ramified self-similar fractals, Ann. Sci. l'École Normale Supérieure 30 (1997) 605-673.

[54]

{54} K.A. Sakallah, T.N. Mudge, O.A. Olukotun, Analysis and design of latch-controlled synchronous digital circuits, IEEE Trans. Comput.-Aided Design Integrated Circuits 11 (3) (1992) 322-333.

Digital Library

[55]

{55} R. Sine, A nonlinear Perron-Frobenius theorem, Proc. AMS 109 (1990) 331-336.

[56]

{56} T. Szymanski, N. Shenoy, Verifying clock schedules, in: Digest of Technical Papers of the IEEE Internat. Conf. Comput.-Aided Design Integrated Circuits, IEEE Computer Society Press, Silver Spring, MD, 1992, pp. 124-131.

Digital Library

[57]

{57} J.M. Vincent, Some ergodic results on stochastic iterative discrete event systems, Discrete Event Dynamic Systems 7 (1997) 209-233.

Digital Library

[58]

{58} N.N. Vorob'ev, Game Theory: Lectures for Economists and Systems Scientists, Applications of Mathematics, Springer, Berlin, 1977.

[59]

{59} C. Wende, Q. Xiangdong, D. Shuhni, The eigen-problem and period analysis of the discrete event System, Systems Sci. Math. Sci. 3 (1990) 243-260.

[60]

{60} W.H.M. Zijm, Asymptotic expansions for dynamic programming recursions with general nonnegative matrices, J. Optim. Theory Appl. 54 (1987) 157-191.

Digital Library

Cited By

Deplano DFranceschelli MGiua A(2018)Lyapunov-Free Analysis for Consensus of Nonlinear Discrete- Time Multi-Agent Systems2018 IEEE Conference on Decision and Control (CDC)10.1109/CDC.2018.8619370(2525-2530)Online publication date: 17-Dec-2018
https://dl.acm.org/doi/10.1109/CDC.2018.8619370
Bolte JGaubert SVigeral G(2015)Definable Zero-Sum Stochastic GamesMathematics of Operations Research10.1287/moor.2014.066640:1(171-191)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1287/moor.2014.0666
Yang YGeilen MBasten TStuijk SCorporaal HRosenstiel WMacii E(2012)Playing games with scenario- and resource-aware SDF graphs through policy iterationProceedings of the Conference on Design, Automation and Test in Europe10.5555/2492708.2492758(194-199)Online publication date: 12-Mar-2012
https://dl.acm.org/doi/10.5555/2492708.2492758
Show More Cited By

Index Terms

From max-plus algebra to nonexpansive mappings: a nonlinear theory for discrete event systems
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
  2. Mathematical analysis
    1. Differential equations
      1. Differential algebraic equations
    2. Numerical analysis
      1. Computations on matrices

Recommendations

Introduction to max-plus algebra
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

This tutorial will focus on the basics of max-plus algebra along with relevant topics. Max-plus algebra is a discrete algebraic system in which the max and plus operations are defined as addition and multiplication in conventional algebra. Using this ...
The QR Decomposition and the Singular Value Decomposition in the Symmetrized Max-Plus Algebra Revisited

This paper is an updated and extended version of the paper "The QR Decomposition and the Singular Value Decomposition in the Symmetrized Max-Plus Algebra" (B. De Schutter and B. De Moor, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 378--406). The max-plus ...
Approximating common fixed points of asymptotically nonexpansive maps in uniformly convex Banach spaces

We introduce three-step iterative schemes with errors for two and three nonexpansive maps and establish weak and strong convergence theorems for these schemes. Mann-type and Ishikawa-type convergence results are included in the analysis of these new ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 293, Issue 1

3 February 2003

232 pages

ISSN:0304-3975

Issue’s Table of Contents

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 03 February 2003

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Deplano DFranceschelli MGiua A(2018)Lyapunov-Free Analysis for Consensus of Nonlinear Discrete- Time Multi-Agent Systems2018 IEEE Conference on Decision and Control (CDC)10.1109/CDC.2018.8619370(2525-2530)Online publication date: 17-Dec-2018
https://dl.acm.org/doi/10.1109/CDC.2018.8619370
Bolte JGaubert SVigeral G(2015)Definable Zero-Sum Stochastic GamesMathematics of Operations Research10.1287/moor.2014.066640:1(171-191)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1287/moor.2014.0666
Yang YGeilen MBasten TStuijk SCorporaal HRosenstiel WMacii E(2012)Playing games with scenario- and resource-aware SDF graphs through policy iterationProceedings of the Conference on Design, Automation and Test in Europe10.5555/2492708.2492758(194-199)Online publication date: 12-Mar-2012
https://dl.acm.org/doi/10.5555/2492708.2492758
Gaubert SKatz R(2006)Max-plus convex geometryProceedings of the 9th international conference on Relational Methods in Computer Science, and 4th international conference on Applications of Kleene Algebra10.1007/11828563_13(192-206)Online publication date: 1-Aug-2006
https://dl.acm.org/doi/10.1007/11828563_13
Wild M(2005)The many benefits of putting stack filters into disjunctive or conjunctive normal formDiscrete Applied Mathematics10.5555/1099040.1704878149:1-3(174-191)Online publication date: 1-Aug-2005
https://dl.acm.org/doi/10.5555/1099040.1704878
Cheng Y(2005)A survey of the theory of min-max systemsProceedings of the 2005 international conference on Advances in Intelligent Computing - Volume Part II10.1007/11538356_64(616-625)Online publication date: 23-Aug-2005
https://dl.acm.org/doi/10.1007/11538356_64
Costan AGaubert SGoubault EMartel MPutot S(2005)A policy iteration algorithm for computing fixed points in static analysis of programsProceedings of the 17th international conference on Computer Aided Verification10.1007/11513988_46(462-475)Online publication date: 6-Jul-2005
https://dl.acm.org/doi/10.1007/11513988_46
Sorin S(2004)Asymptotic Properties of Monotonic Nonexpansive MappingsDiscrete Event Dynamic Systems10.1023/B:DISC.0000005011.93152.d814:1(109-122)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1023/B%3ADISC.0000005011.93152.d8

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents