idempotent semiring

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


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.


  • 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.

Last revised on November 2, 2012 at 23:51:59. See the history of this page for a list of all contributions to it.