Skip to main navigation Skip to search Skip to main content

Max-plus algebraic tools for discrete event systems, static analysis, and zero-sum games

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

The max-plus algebraic approach of timed discrete event systems emerged in the eighties, after the discovery that synchronization phenomena can be modeled in a linear way in the max-plus setting. This led to a number of results, like the determination of long term characteristics (throughput, stationary regime) by spectral theory methods or the representation of the input-output behavior by rational series. Since these early developments, the max-plus scene has considerably evolved. Many analytical results appeared to carry over to a larger class of dynamical systems, involving monotone or nonexpansiveness operators. For instance, discrete dynamics in which the operations of maximum, minimum, positive linear combinations or log-exp type combinations simultaneously appear fall into this class. Such generalizations are based on the study of non-linear fixed point problems by methods of Perron-Frobenius theory. They keep, however, a combinatorial flavor reminiscent of the max-plus case. Then, the same monotone fixed point problems were seen to arise in other fields, including zero-sum games and static analysis by abstract interpretation, leading to the design of algorithms inspired by control and game theory (policy iteration) in static analysis. Finally, the recent flourishing of tropical geometry, in which max-plus objects are thought of as projections of classical objects by some valuations, has motivated new theoretical works, in particular on max-plus polyhedra. The latter were initially used to represent some invariant spaces (like the reachable sets of discrete event systems), they have arisen more recently in relation with game or static analysis problems. They now appear to be mathematical objects of an intrinsic interest, to which the arsenal of algorithms from computational geometry can be adapted. This survey will give a unified perspective on these developments, shedding light on recent results concerning zero-sum games, static analysis, non-linear Perron-Frobenius theory, and polyhedra.

Original languageEnglish
Title of host publicationFormal Modeling and Analysis of Timed Systems - 7th International Conference, FORMATS 2009, Proceedings
PublisherSpringer Verlag
Pages7-11
Number of pages5
ISBN (Print)3642043674, 9783642043673
DOIs
Publication statusPublished - 1 Jan 2009
Event7th International Conference on Formal Modelling and Analysis of Timed Systems, FORMATS 2009 - Budapest, Hungary
Duration: 14 Sept 2009 → 16 Sept 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5813 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Conference on Formal Modelling and Analysis of Timed Systems, FORMATS 2009
Country/TerritoryHungary
CityBudapest
Period14/09/09 → 16/09/09

Fingerprint

Dive into the research topics of 'Max-plus algebraic tools for discrete event systems, static analysis, and zero-sum games'. Together they form a unique fingerprint.

Cite this