An introduction to idempotency

Summary

Introduction

The word idempotency signifies the study of semirings in which the addition operation is idempotent: a + a = a. The best-known example is the max-plus semiring, R U {100}, in which addition is defined as max{a, b} and multiplication as a + b, the latter being distributive over the former. Interest in such structures arose in the 1950s through the observation that certain problems of discrete optimisation could be linearised over suitable idempotent semirings. Cuninghame-Green's pioneering book, [CG79], should be consulted for some of the early references. More recently, intriguing new connections have emerged with automata theory, discrete event systems, nonexpansive mappings, nonlinear partial differential equations, optimisation theory and large deviations, and these topics are discussed further in the subsequent sections of this paper. The phrase idempotent analysis first appears in the work of Kolokoltsov and Maslov, [KM89].

Idempotency has arisen from a variety of sources and the different strands have not always paid much attention to each other's existence. This has led to a rather parochial view of the subject and its place within mathematics; it is not as well-known nor as widely utilised as perhaps it should be. The workshop on which this volume is based was organised, in part, to address this issue. With this in mind, we have tried to present here a coherent account of the subject from a mathematical perspective while at the same time providing some background to the other papers in this volume. We have said rather little about what are now standard topics treated in the main books in the field, [CG79, Zim81, CKR84, BCOQ92, MK94, KMa] and [Mas87a, Chapter VIII].