Namespaces
Variants
Actions

Difference between revisions of "Idempotent semi-ring"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (→‎References: isbn link)
 
(10 intermediate revisions by one other user not shown)
Line 1: Line 1:
 
''dioid''
 
''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" />:
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i1100407.png" /> (idempotent addition);
+
i) $a \oplus a = a$ (idempotent addition);
  
ii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i1100408.png" />;
+
ii) $a \oplus (b \oplus c) = (a \oplus b) \oplus c$;
  
iii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i1100409.png" />;
+
iii) $a \oplus b = b \oplus a$;
  
iv) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004010.png" />;
+
iv) $0 \oplus a = a \oplus 0 = a$;
  
v) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004011.png" />;
+
v) $0 \odot a = a \odot 0 = 0$;
  
vi) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004012.png" />;
+
vi) $1 \odot a = a \odot 1 = a$;
  
vii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004013.png" />;
+
vii) $a \odot (c \oplus c) = (a \odot b) \oplus (a \odot c)$;
  
viii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110040/i11004014.png" />.
+
viii) $(b \oplus c) \odot a = (b \odot a) \oplus (c \odot a)$.
  
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]]]).
+
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.===
 
===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.
+
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.===
 
===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" />.
+
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.===
 
===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).
+
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.===
 
===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.
+
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|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]]].
+
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, <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.
+
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 [[Transitive relation|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 $a,b,c \in A$ one has $a \oplus c \le b \oplus c$, and $a \odot c \le b \odot c$ if $a \le b$. Using this standard partial order it is possible to define in the usual way the notions of upper and lower bounds, bounded sets, $\sup M$ (and $\inf N$) for upper- (lower-) bounded sets $M$ (respectively, $N$), 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.
+
If the multiplication in a semi-ring $A$ is invertible on $A \setminus \{0\}$, then $A$ is called a semi-field. For example, $\mathbf{R}_{\max}$ is a semi-field. Idempotent semi-fields and semi-rings with idempotent multiplication are especially interesting.
  
 
====References====
 
====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. I. Newton Institute'' , Cambridge Univ. Press  (in press)</TD></TR></table>
+
<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. Cuninghame-Green,  "Minimax algebra" , ''Lecture Notes in Economics and Mathematical Systems'' , '''166''' , Springer  (1979) {{ISBN|3-540-09113-0}} {{ZBL|0399.90052}}</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|done}}

Latest revision as of 20:42, 16 November 2023

dioid

A semi-ring with idempotent addition. So, a set $A$ equipped with binary operations $\oplus$ (addition) and $\odot$ (multiplication) and neutral elements $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. [a1], [a2], [a3], [a4], [a5], [a6], [a7], [a8], [a9], [a10]. Idempotent semi-rings are often called dioids, see e.g. [a3], [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 [a1], [a2], [a3], [a4], [a5], [a6], [a7], [a8], [a9], [a10], [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. [a1], [a2], [a3], [a4], [a5], [a6], [a7], [a8], [a9], [a10], [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 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 $a,b,c \in A$ one has $a \oplus c \le b \oplus c$, and $a \odot c \le b \odot c$ if $a \le b$. Using this standard partial order it is possible to define in the usual way the notions of upper and lower bounds, bounded sets, $\sup M$ (and $\inf N$) for upper- (lower-) bounded sets $M$ (respectively, $N$), etc.

If the multiplication in a semi-ring $A$ is invertible on $A \setminus \{0\}$, then $A$ is called a semi-field. For example, $\mathbf{R}_{\max}$ is a semi-field. Idempotent semi-fields and semi-rings with idempotent multiplication are especially interesting.

References

[a1] A.V. Aho, J.E. Hopcroft, J.D. Ullman, "The design and analysis of computer algorithms" , Addison-Wesley (1976)
[a2] B.A. Carré, "Graphs and networks" , Clarendon Press and Oxford Univ. Press (1979)
[a3] M. Gondran, M. Minoux, "Graphes et algorithms" , Ed. Eyrolles (1979; 1988)
[a4] R.A. Cuninghame-Green, "Minimax algebra" , Lecture Notes in Economics and Mathematical Systems , 166 , Springer (1979) ISBN 3-540-09113-0 Zbl 0399.90052
[a5] U. Zimmermann, "Linear and combinatorial optimization in ordered algebraic structures" Ann. Discrete Math. , 10 (1981) pp. 1–380
[a6] "Mathematical aspects of computer engineering" V.P. Maslov (ed.) K.A. Volosov (ed.) , MIR (1988) (In Russian)
[a7] "Idempotent analysis" V.P. Maslov (ed.) S.N. Samborskii (ed.) , Amer. Math. Soc. (1992) (In Russian)
[a8] V.N. Kolokoltsov, V.P. Maslov, "Idempotent analysis and applications" , Kluwer Acad. Publ. (1996) (In Russian)
[a9] F.L. Baccelli, G. Cohen, G.J. Olsder, J.-P. Quadrat, "Synchronization and linearity: an algebra for discrete event systems" , Wiley (1992)
[a10] 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)
[a11] "Idempotency" J. Gunawardena (ed.) , Publ. Isaac Newton Institute 11, Cambridge Univ. Press (1998) ISBN 0-521-55344-X Zbl 0882.00035
How to Cite This Entry:
Idempotent semi-ring. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Idempotent_semi-ring&oldid=16503
This article was adapted from an original article by G.L. Litvinov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article