nLab
idempotent semiring

Idempotent semirings

Idea

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 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=xx + x = x, for all xRx\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=LLL + 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)