HP Labs Technical Reports



Click here for full text: PDF

An Introduction to Idempotency

Gunawardena, Jeremy

HPL-BRIMS-96-24

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 best-known example is the max-plus 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 Hewlett-Packard'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

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map] [Home] [Hewlett-Packard]