idempotent semiring

Idempotent semirings

Idempotent semirings


Recall that a semiring is a set RR equipped with two binary operations, denoted ++, and \cdot and called addition and multiplication, satisfying the ring (or rng) axioms except that there may or may not be either be a zero nor a negative nor an inverse, for which reason do check.


An idempotent semiring (also known as a dioid) is one in which addition is idempotent: x+x=xx + x = x, for all xRx\in R.


The term dioid is sometimes used as an alternative name for idempotent semirings.

From now on we will assume that the semiring, SS, has a neutral element ε\varepsilon for + and one ee for \cdot. Moreover we assume that for all sSs\in S, sε=εs=εs\cdot \varepsilon =\varepsilon s = \varepsilon.


On an idempotent semiring, SS, there is a partial order given by

xy:x+y=y. x \leq y : \iff x + y = y.

To check transitivity observe that xy x \leq y and yz y \leq z imply z=yzy+z=xy(x+y)+z=x+(y+z)=yzx+z z \stackrel{y \leq z}{=} y + z \stackrel{x \leq y}{=} (x + y) + z = x + (y + z) \stackrel{y \leq z}{=} x + z . Due to idempotence the addition is a join with respect to this partial order: take a zz such that xzx\leq z and yzy\leq z, then z=z+z=x+z+y+z=x+y+zz = z + z = x + z + y + z = x + y + z. The partial order is preserved by multiplication.


  • Any quantale is an idempotent semiring, or dioid, under join and multiplication.

  • The set of languages over a given alphabet AA forms an idempotent semiring in which L+L=LLL + L' = L \cup L' and multiplication is given by concatenation. In fact this is a quantale P(A *)P(A^\ast) where the multiplication is the 2\mathbf{2}-enriched Day convolution product induced from the monoid multiplication of the free monoid A *A^\ast.

  • The tropical algebra and the max-plus algebra are idempotent semirings.

  • Given an idempotent semiring RR one can form the weak interval extension I(R)I(R). This is the idempotent semiring defined on all close intervals [x,y]={zRxzy}[x, y] = \{ z \in R \mid x \leq z \leq y \} by the operations [x,y]+[x,y]=[x+x,y+y][x, y] + [x', y'] = [x + x', y + y'] and [x,y][x,y]=[xx,yy][x, y] \cdot [x', y'] = [x \cdot x', y \cdot y']. The multiplicative unit is given by [1,1][1,1] and, if RR has an additive unit 00, an additive unit is given by [0,0][0,0].

Last revised on September 9, 2021 at 07:42:51. See the history of this page for a list of all contributions to it.