An Introduction to Idempotency - HP Labs

an introduction to the volume ofproceedings for the workshop on Idempotency ...... priate rule schemes, computer scientists have defined classes of automata-.
2MB Sizes 2 Downloads 167 Views
rhO' HEWLETT ~f..l PACKA~D

An Introduction to Idempotency Jeremy Gunawardena Basic Research Institute in the Mathematical Sciences HP Laboratories Bristol HPL-BRIMS-96-24 September, 1996

Internal Accession Date Only

The word idempotency siwfies the study of semirings in wmch the addition operation is idempotent: a + a = a. The best-mown 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 distnbutive 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 ~triguing connections with ~.hscrete e~ent syste~sl automata . theory, nonexpanSlVe mappmgs, nonlmear partla differential equations, optunisation theory and large deviations. TIle 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 viewpoin1 of the recent developments in the subject. iDe major open problems are pointed out and an extensive bibliography is provided.

© Copyright Hewlett-Packard Company 1996

An Introduction to Idempotency Jeremy Gunawardena 1

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, JR U { -00 }, 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. Vole 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]. We have tried instead to direct the reader towards the open problems and the newer developments, while pointing out the links with other areas of mathematics. However, we make no pretence at completeness. A different view of the subject is put forward by Litvinov and Maslov in their survey paper in this volume, [LM]. Stephane Gaubert and Jean Mairesse provided the author with extensive and detailed suggestions on the first draft of this paper. It is a pleasure to thank them, as well as Fran(,;ois Baccelli, Grigori Litvinov, Pierre del Moral and Jacques Sakarovitch, for their comments, which resulted in many corrections and improvements. Any errors or omissions that remain are entirely the responsibility of the author.

Jeremy Gunawardena

2

2

Dioids