Some automata-theoretic aspects of min-max-plus semirings

Summary

Abstract

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 ℝ equiped with min, max or + as sum and/or product. We here address three types of properties related to rational series with multiplicities in such semirings: structure of supports, decidability of equality and inequality problems, and Fatou properties.

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, like 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 similar objects were studied for Artificial Intelligence purposes: the fuzzy calculus involves indeed essentially (min, max) semirings (see [3] for more details and extensive references on this area).

More recently, the min–max–plus techniques have also appeared in formal language theory: the so-called tropical semiring, i.e. ℳ = (ℕ∪{+ ∞}, min, +), played indeed a central role in the study and solution of the finite power problem for rational languages (which is the problem of deciding whether the star of a given rational language L is equal to some finite union of iterated concatenations of L; cf. [6]).