Preface

Summary

This volume arose out of a workshop on Idempotency that was held at Hewlett-Packard's Basic Research Institute in the Mathematical Sciences (BRIMS) from 3–7 October 1994.

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, ℝ U {−∈}, 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 late 1950s through the observation that certain problems of discrete optimisation could be linearised over suitable idempotent semirings. More recently the subject has established rich connections with automata theory, discrete event systems, nonexpansive mappings, nonlinear partial differential equations, optimisation theory and large deviations. These new developments are the focus of this volume.

The papers brought together here consist of expanded contributions to the BRIMS workshop as well as some invited contributions. The papers were all reviewed, in each case by at least one person who was not associated with the workshop. Although the level of acceptance was more relaxed than for a journal, the reviewing process was conducted seriously. Not all the contributions were accepted and many of those that were have been substantially improved as a result of the reviews. I am grateful to all the reviewers for their time and effort and I regret that, for reasons of confidentiality, it does not seem appropriate to mention their names here.