View source for Idempotent semi-ring

''dioid''

A [[Semi-ring|semi-ring]] with idempotent addition. So, a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i1100401.png" /> equipped with binary operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i1100402.png" /> (addition) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i1100403.png" /> (multiplication) and neutral elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i1100404.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i1100405.png" /> is called an idempotent semi-ring if the following basic properties are valid for all elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i1100406.png" />:

i) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i1100407.png" /> (idempotent addition);

ii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i1100408.png" />;

iii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i1100409.png" />;

iv) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004010.png" />;

v) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004011.png" />;

vi) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004012.png" />;

vii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004013.png" />;

viii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004014.png" />.

An idempotent semi-ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004015.png" /> is commutative if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004016.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004017.png" />. 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|idempotent analysis]]. This concept has many applications in different optimization problems (including [[Dynamic programming|dynamic programming]]), computer science, automata and formal language theory, numerical methods, [[Parallel programming|parallel programming]], etc. (cf. also [[Idempotent algorithm|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004018.png" /> be the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004019.png" /> (where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004020.png" /> is the field of real numbers) equipped with the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004021.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004022.png" /> (usual addition); set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004024.png" />. Similarly, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004025.png" /> be the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004026.png" /> equipped with the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004027.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004028.png" />; in this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004030.png" />. It is easy to check that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004031.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004032.png" /> are (isomorphic) commutative idempotent semi-rings.

===Example 2.===
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004033.png" /> be the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004034.png" /> of all non-negative real numbers endowed with the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004036.png" /> (usual multiplication); <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004037.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004038.png" />. This idempotent semi-ring is isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004039.png" />. The isomorphism is given by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004040.png" />.

===Example 3.===
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004041.png" /> with the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004042.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004043.png" /> and neutral elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004044.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004045.png" /> (the cases <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004046.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004047.png" /> are possible).

===Example 4.===
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004048.png" /> be the set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004049.png" />-matrices with entries belonging to an idempotent semi-ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004050.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004051.png" /> is a non-commutative idempotent semi-ring with respect to matrix addition and matrix multiplication.

The [[Boolean algebra|Boolean algebra]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004052.png" /> 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, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004053.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004054.png" />. For this relation, [[Reflexivity|reflexivity]] is equivalent to idempotency of the (generalized) addition, whereas [[Transitivity|transitivity]], respectively anti-symmetry, follow from associativity, respectively commutativity, of this operation. On <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004055.png" /> (and also on the semi-rings described in the Examples 2 and 3), this ordering relation coincides with the natural one; on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004056.png" /> it is the opposite of the natural ordering relation on the real axis. Every element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004057.png" /> in an idempotent semi-ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004058.png" /> is  "non-negative" : <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004059.png" />. Indeed, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004060.png" />. 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>