Some automata-theoretic aspects of Min-Max-Plus semirings

This paper is devoted to the survey of some automata-theoretic aspects of different exotic semirings, i.e. semirings whose underlying set is some subset of R equiped with min, max or + as sum and/or product. We here adress three types of properties related with rational series with multiplicities in such semirings : structure of supports, decidability of equality and inequality problems, Fatou properties. 1 Introduction Min--max--plus computations are used in several areas. These techniques appeared initially in the seventies in the context of Operations Research for analyzing discrete event systems (cf Chapter 3 of [5]; see also [1] for a survey of these aspects of the theory). In another direction, the (min= max; +) semirings were also used in mathematical physics in the study of several partial differential equations which, as the Hamilton-Jacobi equation, appeared to be (min; +)-linear (see for instance the last chapter of Maslov's book [9]). It is also interesting to observe that..