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 not be a zero nor a negative.

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.

Examples

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

• The powerset of the set of languages over a given alphabet forms an idempotent semiring in which $L + L' = L \cup L'$ and multiplication is given by concatentation.

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

Revised on November 2, 2012 23:51:59 by Anonymous Coward (64.89.53.240)