Idempotent semirings

Idea

Recall that a semiring is a set $R$ 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.

Definition

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

Terminology

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

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

Properties

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

To check transitivity observe that $x \leq y$ and $y \leq z$ imply $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 $z$ such that $x\leq z$ and $y\leq z$, then $z = z + z = x + z + y + z = x + y + z$. The partial order is preserved by multiplication.

Examples

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

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

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

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

Related concepts

• ring
• rig
• idempotent semifield
• tropical semiring
• max-plus algebra
• residuated idempotent semiring