View source for Idempotent semi-ring

''dioid''

A [[Semi-ring|semi-ring]] with idempotent addition. So, a set $A$ equipped with binary operations $\oplus$ (addition) and $\odot$ (multiplication) and [[neutral element]]s $0$ and $1$ is called an idempotent semi-ring if the following basic properties are valid for all elements $a,b,c \in A$:

i) $a \oplus a = a$ (idempotent addition);

ii) $a \oplus (b \oplus c) = (a \oplus b) \oplus c$;

iii) $a \oplus b = b \oplus a$;

iv) $0 \oplus a = a \oplus 0 = a$;

v) $0 \odot a = a \odot 0 = 0$;

vi) $1 \odot a = a \odot 1 = a$;

vii) $a \odot (c \oplus c) = (a \odot b) \oplus (a \odot c)$;

viii) $(b \oplus c) \odot a = (b \odot a) \oplus (c \odot a)$.

An idempotent semi-ring $A$ is commutative if $a \odot b = b \odot a$ for all $a,b \in A$. Different versions of this axiomatics are used, see e.g. [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]], [[#References|[a8]]], [[#References|[a9]]], [[#References|[a10]]]. Idempotent semi-rings are often called dioids, see e.g. [[#References|[a3]]], [[#References|[a9]]]. The concept of an idempotent semi-ring is a basic concept in [[idempotent analysis]]. This concept has many applications in different optimization problems (including [[dynamic programming]]), computer science, automata and formal language theory, numerical methods, [[parallel programming]], etc. (cf. also [[Idempotent algorithm]] and [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]], [[#References|[a8]]], [[#References|[a9]]], [[#References|[a10]]], [[#References|[a11]]]).

===Example 1.===
Let $\mathbf{R}_{\max}$ be the set $A = \mathbf{R} \cup \{-\infty\}$ (where $\mathbf{R}$ is the field of real numbers) equipped with the operations $\oplus = {\max}$ and $\odot = {+}$ (usual addition); set $\mathbf{0} = -\infty$, $\mathbf{1} = 0$. Similarly, let $\mathbf{R}_{\min}$ be the set $\mathbf {R} \cup \{+\infty\}$ equipped with the operations $\oplus = {\min}$ and $\odot = {+}$; in this case $\mathbf{0} = +\infty$ and $\mathbf{1} = 0$. It is easy to check that $\mathbf{R}_{\max}$ and $\mathbf{R}_{\min}$ are (isomorphic) commutative idempotent semi-rings.

===Example 2.===
Let $A$ be the set $\mathbf{R}_{+}$ of all non-negative real numbers endowed with the operations $\oplus={\max}$ and $\odot = {\times}$ (usual multiplication); $\mathbf{0} = 0$, $\mathbf{1} = 1$. This idempotent semi-ring is isomorphic to $\mathbf{R}_{\max}$. The isomorphism is given by $x \mapsto \log x$.

===Example 3.===
Let $A = [a,b] = \{x \in \mathbf{R} : a \le x \le b \}$ with the operations $\oplus = {\max}$, $\odot = {\min}$ and neutral elements $\mathbf{0} = a$, $\mathbf{1} = b$ (the cases $a = -\infty$, $b = +\infty$ are possible).

===Example 4.===
Let $\mathrm{Mat}_n(A)$ be the set of $n \times n$-matrices with entries belonging to an idempotent semi-ring $A$. Then $\mathrm{Mat}_n(A)$ is a non-commutative idempotent semi-ring with respect to matrix addition and matrix multiplication.

The [[Boolean algebra]] $\mathcal{B}_2 = \{\mathbf{0},\mathbf{1}\}$ is an example of a finite idempotent semi-ring. There are many other interesting examples of idempotent semi-rings, see e.g. [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]], [[#References|[a8]]], [[#References|[a9]]], [[#References|[a10]]], [[#References|[a11]]].

There is a natural partial order on any idempotent semi-ring (as well as on any idempotent semi-group; cf. also Idempotent semi-ring). By definition, $a \le b$ if and only if $a \oplus b = b$. For this relation, [[reflexivity]] is equivalent to idempotency of the (generalized) addition, whereas [[transitivity]], respectively [[Symmetry (of a relation)|anti-symmetry]], follow from associativity, respectively commutativity, of this operation. On $\mathbf{R}_{\max}$ (and also on the semi-rings described in the Examples 2 and 3), this ordering relation coincides with the natural one; on $\mathbf{R}_{\min}$ it is the opposite of the natural ordering relation on the real axis. Every element $a$ in an idempotent semi-ring $A$ is  "non-negative" : $0 \le a$. Indeed, $0 \oplus a = a$. Similarly, for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004061.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004062.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004063.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004064.png" />. Using this standard partial order it is possible to define in the usual way the notions of upper and lower bounds, bounded sets, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004065.png" /> (and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004066.png" />) for upper- (lower-) bounded sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004067.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004068.png" />), etc.

If the multiplication in a semi-ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004069.png" /> is invertible on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004070.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004071.png" /> is called a semi-field. For example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004072.png" /> is a semi-field. Idempotent semi-fields and semi-rings with idempotent multiplication are especially interesting.

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  A.V. Aho,   J.E. Hopcroft,   J.D. Ullman,   "The design and analysis of computer algorithms" , Addison-Wesley  (1976)</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  B.A. Carré,   "Graphs and networks" , Clarendon Press and Oxford Univ. Press  (1979)</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  M. Gondran,   M. Minoux,   "Graphes et algorithms" , Ed. Eyrolles  (1979; 1988)</TD></TR>
<TR><TD valign="top">[a4]</TD> <TD valign="top">  R.A. Cuningham-Green,   "Minimax algebra" , ''Lecture Notes in Economics and Mathematical Systems'' , '''166''' , Springer  (1979)</TD></TR>
<TR><TD valign="top">[a5]</TD> <TD valign="top">  U. Zimmermann,   "Linear and combinatorial optimization in ordered algebraic structures"  ''Ann. Discrete Math.'' , '''10'''  (1981)  pp. 1–380</TD></TR>
<TR><TD valign="top">[a6]</TD> <TD valign="top">  "Mathematical aspects of computer engineering"  V.P. Maslov (ed.)  K.A. Volosov (ed.) , MIR  (1988)  (In Russian)</TD></TR>
<TR><TD valign="top">[a7]</TD> <TD valign="top">  "Idempotent analysis"  V.P. Maslov (ed.)  S.N. Samborskii (ed.) , Amer. Math. Soc.  (1992)  (In Russian)</TD></TR>
<TR><TD valign="top">[a8]</TD> <TD valign="top">  V.N. Kolokoltsov,   V.P. Maslov,   "Idempotent analysis and applications" , Kluwer Acad. Publ.  (1996)  (In Russian)</TD></TR>
<TR><TD valign="top">[a9]</TD> <TD valign="top">  F.L. Baccelli,   G. Cohen,   G.J. Olsder,   J.-P. Quadrat,   "Synchronization and linearity: an algebra for discrete event systems" , Wiley  (1992)</TD></TR>
<TR><TD valign="top">[a10]</TD> <TD valign="top">  J.S. Golan,   "The theory of semirings with applications in mathematics and theoretical computer science" , ''Pitman monographs and surveys in pure and applied mathematics'' , '''54''' , Longman  (1992)</TD></TR>
<TR><TD valign="top">[a11]</TD> <TD valign="top">  "Idempotency"  J. Gunawardena (ed.) , ''Publ. Isaac Newton Institute'' '''11''', Cambridge Univ. Press  (1998) ISBN 0-521-55344-X {{ZBL|0882.00035}}</TD></TR>
</table>

{{TEX|part}}