Recall that a semiring is a set equipped with two binary operations, denoted , and 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: , for all .
The term dioid is sometimes used as an alternative name for idempotent semirings.
From now on we will assume that the semiring, , has a neutral element for + and one for . Moreover we assume that for all , .
On an idempotent semiring, , there is a partial order given by
To check transitivity observe that and imply . Due to idempotence the addition is a join with respect to this partial order: take a such that and , then . 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 forms an idempotent semiring in which and multiplication is given by concatenation. In fact this is a quantale where the multiplication is the -enriched Day convolution product induced from the monoid multiplication of the free monoid .
The tropical algebra and the max-plus algebra are idempotent semirings.
Given an idempotent semiring one can form the weak interval extension . This is the idempotent semiring defined on all close intervals by the operations and . The multiplicative unit is given by and, if has an additive unit , an additive unit is given by .
Last revised on September 9, 2021 at 11:42:51. See the history of this page for a list of all contributions to it.