
HP Labs Technical Reports
Click here for full text:
An Introduction to Idempotency
Gunawardena, Jeremy
HPLBRIMS9624
Keyword(s): No keywords available.
Abstract: The word idempotency signifies the study of semirings in which the addition operation is idempotent: a + a =a. The bestknown example is the maxplus semiring, consisting of the real numbers with negative infinity adjoined, 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 intriguing connections with automata theory, discrete event systems, nonexpansive mappings, nonlinear partial differential equations, optimisation theory and large deviations. The present paper was commissioned as an introduction to the volume of proceedings for the workshop on Idempotency held at HewlettPackard's Basic Research Institute in the Mathematical Sciences (BRIMS) in October 1994. It aims to give an introductory survey, from a coherent mathematical viewpoint, of the recent developments in the subject. The major open problems are pointed out and an extensive bibliography is provided.
Back to Index
