Inabstract algebra, asemiring is analgebraic structure. Semirings are a generalization ofrings, dropping the requirement that each element must have anadditive inverse. At the same time, semirings are a generalization ofboundeddistributive lattices.

The smallest semiring that is not a ring is thetwo-element Boolean algebra, for instance withlogical disjunction${\displaystyle \vee }$ as addition. A motivating example that is neither a ring nor a lattice is the set ofnatural numbers${\displaystyle \mathbb{N}}$ (including zero) under ordinary addition and multiplication. Semirings are abundant because a suitable multiplication operation arises as thefunction composition ofendomorphisms over anycommutative monoid.

Some authors define semirings without the requirement for there to be a${\displaystyle 0}$ or${\displaystyle 1}$. This makes the analogy betweenring andsemiring on the one hand andgroup andsemigroup on the other hand work more smoothly. These authors often userig for the concept defined here.^[1][a] This originated as a joke, suggesting that rigs are rings withoutnegative elements. (Akin to usingrng to mean a ring without a multiplicativeidentity.)

The termdioid (for "double monoid") has been used to mean semirings or other structures. It was used by Kuntzmann in 1972 to denote a semiring.^[2] (It is alternatively sometimes used fornaturally ordered semirings^[3] but the term was also used for idempotent subgroups byBaccelli et al. in 1992.^[4])

Asemiring is aset${\displaystyle R}$ equipped with twobinary operations${\displaystyle +}$ and${\displaystyle \cdot ,}$ called addition and multiplication, such that:^[5][6][7]

• ${\displaystyle (R,+)}$ is acommutativemonoid with anidentity element called${\displaystyle 0}$:
  • ${\displaystyle (a+b)+c=a+(b+c)}$
  • ${\displaystyle 0+a=a}$
  • ${\displaystyle a+0=a}$
  • ${\displaystyle a+b=b+a}$
• ${\displaystyle (R,\cdot )}$ is a monoid with an identity element called${\displaystyle 1}$:
  • ${\displaystyle (a\cdot b)\cdot c=a\cdot (b\cdot c)}$
  • ${\displaystyle 1\cdot a=a}$
  • ${\displaystyle a\cdot 1=a}$

Further, the following axioms tie to both operations:

• Through multiplication, any element is left- and right-annihilated by the additive identity:
  • ${\displaystyle 0\cdot a=0}$
  • ${\displaystyle a\cdot 0=0}$
• Multiplication left- and right-distributes over addition:
  • ${\displaystyle a\cdot (b+c)=(a\cdot b)+(a\cdot c)}$
  • ${\displaystyle (b+c)\cdot a=(b\cdot a)+(c\cdot a)}$

The symbol${\displaystyle \cdot }$ is usually omitted from the notation; that is,${\displaystyle a\cdot b}$ is just written${\displaystyle ab.}$

Similarly, anorder of operations is conventional, in which${\displaystyle \cdot }$ is applied before${\displaystyle +}$. That is,${\displaystyle a+b\cdot c}$ denotes${\displaystyle a+(b\cdot c)}$.

For the purpose of disambiguation, one may write${\displaystyle 0_R}$ or${\displaystyle 1_R}$ to emphasize which structure the units at hand belong to.

If${\displaystyle x\in R}$ is an element of a semiring and${\displaystyle n\in \mathbb{N}}$, then${\displaystyle n}$-times repeated multiplication of${\displaystyle x}$ with itself is denoted${\displaystyle x^n}$, and one similarly writes${\displaystyle xn:=x+x+\cdots +x}$ for the${\displaystyle n}$-times repeated addition.

Thezero ring with underlying set${\displaystyle \{0\}}$ is a semiring called the trivial semiring. This triviality can be characterized via${\displaystyle 0=1}$ and so when speaking of nontrivial semirings,${\displaystyle 0\ne 1}$ is often silently assumed as if it were an additional axiom.Now given any semiring, there are several ways to define new ones.

As noted, the natural numbers${\displaystyle \mathbb{N}}$ with its arithmetic structure form a semiring. Taking the zero and the image of the successor operation in a semiring${\displaystyle R}$, i.e., the set${\displaystyle \{x\in R\mid x=0_R\vee \mathrm{\exists }p.x=p+1_R\}}$ together with the inherited operations, is always a sub-semiring of${\displaystyle R}$.

If${\displaystyle (M,+)}$ is a commutative monoid, function composition provides the multiplication to form a semiring: The set${\displaystyle \mathrm{End}(M)}$ of endomorphisms${\displaystyle M\to M}$ forms a semiring where addition is defined from pointwise addition in${\displaystyle M}$. Thezero morphism and the identity are the respective neutral elements. If${\displaystyle M=R^n}$ with${\displaystyle R}$ a semiring, we obtain a semiring that can be associated with the square${\displaystyle n\times n}$matrices${\displaystyle {\mathcal{M}}_n(R)}$ with coefficients in${\displaystyle R}$, thematrix semiring using ordinaryaddition andmultiplication rules of matrices. Given${\displaystyle n\in \mathbb{N}}$ and${\displaystyle R}$ a semiring,${\displaystyle {\mathcal{M}}_n(R)}$ is always a semiring also. It is generally non-commutative even if${\displaystyle R}$ was commutative.

Dorroh extensions: If${\displaystyle R}$ is a semiring, then${\displaystyle R\times \mathbb{N}}$ with pointwise addition and multiplication given by${\displaystyle ⟨x,n⟩\bullet ⟨y,m⟩:=⟨x\cdot y+(xm+yn),n\cdot m⟩}$ defines another semiring with multiplicative unit${\displaystyle 1_{R\times \mathbb{N}}:=⟨0_R,1_{\mathbb{N}}⟩}$. Very similarly, if${\displaystyle N}$ is any sub-semiring of${\displaystyle R}$, one may also define a semiring on${\displaystyle R\times N}$, just by replacing the repeated addition in the formula by multiplication. Indeed, these constructions even work under looser conditions, as the structure${\displaystyle R}$ is not actually required to have a multiplicative unit.

Zerosumfree semirings are in a sense furthest away from being rings. Given a semiring, one may adjoin a new zero${\displaystyle 0^{\prime }}$ to the underlying set and thus obtain such a zerosumfree semiring that also lackszero divisors. In particular, now${\displaystyle 0\cdot 0^{\prime }=0^{\prime }}$ and the old semiring is actually not a sub-semiring. One may then go on and adjoin new elements "on top" one at a time, while always respecting the zero. These two strategies also work under looser conditions. Sometimes the notations${\displaystyle -\mathrm{\infty }}$ resp.${\displaystyle +\mathrm{\infty }}$ are used when performing these constructions.

Adjoining a new zero to the trivial semiring, in this way, results in another semiring which may be expressed in terms of thelogical connectives of disjunction and conjunction:${\displaystyle ⟨\{0,1\},+,\cdot ,⟨0,1⟩⟩=⟨\{\mathrm{\perp },\mathrm{\top }\},\vee ,\wedge ,⟨\mathrm{\perp },\mathrm{\top }⟩⟩}$. Consequently, this is the smallest semiring that is not a ring. Explicitly, it violates the ring axioms as${\displaystyle \mathrm{\top }\vee P=\mathrm{\top }}$ for all${\displaystyle P}$, i.e.${\displaystyle 1}$ has no additive inverse. In theself-dual definition, the fault is with${\displaystyle \mathrm{\perp }\wedge P=\mathrm{\perp }}$. (This is not to be conflated with the ring${\displaystyle {\mathbb{Z}}_2}$, whose addition functions asxor${\displaystyle ⊻}$.) In thevon Neumann model of the naturals,${\displaystyle 0_{\omega }:=\{\}}$,${\displaystyle 1_{\omega }:=\{0_{\omega }\}}$ and${\displaystyle 2_{\omega }:=\{0_{\omega },1_{\omega }\}=\mathcal{P}{1}_{\omega }}$. The two-element semiring may be presented in terms of the set theoretic union and intersection as${\displaystyle ⟨\mathcal{P}{1}_{\omega },\cup ,\cap ,⟨\{\},1_{\omega }⟩⟩}$. Now this structure in fact still constitutes a semiring when${\displaystyle 1_{\omega }}$ is replaced by any inhabited set whatsoever.

Theideals on a semiring${\displaystyle R}$, with their standard operations on subset, form a lattice-ordered, simple and zerosumfree semiring. The ideals of${\displaystyle {\mathcal{M}}_n(R)}$ are in bijection with the ideals of${\displaystyle R}$. The collection of left ideals of${\displaystyle R}$ (and likewise the right ideals) also have much of that algebraic structure, except that then${\displaystyle R}$ does not function as a two-sided multiplicative identity.

If${\displaystyle R}$ is a semiring and${\displaystyle A}$ is aninhabited set,${\displaystyle A^{\ast }}$ denotes thefree monoid and the formal polynomials${\displaystyle R[A^{\ast }]}$ over its words form another semiring. For small sets, the generating elements are conventionally used to denote the polynomial semiring. For example, in case of a singleton${\displaystyle A=\{X\}}$ such that${\displaystyle A^{\ast }=\{\epsilon ,X,X^2,X^3,\dots \}}$, one writes${\displaystyle R[X]}$. Zerosumfree sub-semirings of${\displaystyle R}$ can be used to determine sub-semirings of${\displaystyle R[A^{\ast }]}$.

Given a set${\displaystyle A}$, not necessarily just a singleton, adjoining a default element to the set underlying a semiring${\displaystyle R}$ one may define the semiring of partial functions from${\displaystyle A}$ to${\displaystyle R}$.

Given aderivation${\displaystyle \mathrm{d}}$ on a semiring${\displaystyle R}$, another the operation "${\displaystyle \bullet }$" fulfilling${\displaystyle X\bullet y=y\bullet X+\mathrm{d}(y)}$ can be defined as part of a new multiplication on${\displaystyle R[X]}$, resulting in another semiring.

The above is by no means an exhaustive list of systematic constructions.

Derivations on a semiring${\displaystyle R}$ are the maps${\displaystyle \mathrm{d}:R\to R}$ with${\displaystyle \mathrm{d}(x+y)=\mathrm{d}(x)+\mathrm{d}(y)}$ and${\displaystyle \mathrm{d}(x\cdot y)=\mathrm{d}(x)\cdot y+x\cdot \mathrm{d}(y)}$.

For example, if${\displaystyle E}$ is the${\displaystyle 2\times 2}$ unit matrix and, then the subset of${\displaystyle {\mathcal{M}}_2(R)}$ given by the matrices${\displaystyle aE+bU}$ with${\displaystyle a,b\in R}$ is a semiring with derivation${\displaystyle aE+bU\mapsto bU}$.

A basic property of semirings is that${\displaystyle 1}$ is not a left or rightzero divisor, and that${\displaystyle 1}$ but also${\displaystyle 0}$ squares to itself, i.e. these have${\displaystyle u^2=u}$.

Some notable properties are inherited from the monoid structures: The monoid axioms demand unit existence, and so the set underlying a semiring cannot be empty. Also, the2-ary predicate${\displaystyle x{\le }_{\text{pre}}y}$ defined as${\displaystyle \mathrm{\exists }d.x+d=y}$, here defined for the addition operation, always constitutes the rightcanonicalpreorder relation.Reflexivity${\displaystyle y{\le }_{\text{pre}}y}$ is witnessed by the identity. Further,${\displaystyle 0{\le }_{\text{pre}}y}$ is always valid, and so zero is theleast element with respect to this preorder. Considering it for the commutative addition in particular, the distinction of "right" may be disregarded. In the non-negative integers${\displaystyle \mathbb{N}}$, for example, this relation isanti-symmetric andstrongly connected, and thus in fact a (non-strict)total order.

Below, more conditional properties are discussed.

Anyfield is also asemifield, which in turn is a semiring in which also multiplicative inverses exist.

Any field is also aring, which in turn is a semiring in which also additive inverses exist. Note that a semiring omits such a requirement, i.e., it requires only acommutative monoid, not acommutative group. The extra requirement for a ring itself already implies the existence of a multiplicative zero. This contrast is also why for the theory of semirings, the multiplicative zero must be specified explicitly.

Here${\displaystyle -1}$, the additive inverse of${\displaystyle 1}$, squares to${\displaystyle 1}$. As additive differences${\displaystyle d=y-x}$ always exist in a ring,${\displaystyle x{\le }_{\text{pre}}y}$ is a trivial binary relation in a ring.

A semiring is called acommutative semiring if also the multiplication is commutative.^[8] Its axioms can be stated concisely: It consists of two commutative monoids${\displaystyle ⟨+,0⟩}$ and${\displaystyle ⟨\cdot ,1⟩}$ on one set such that${\displaystyle a\cdot 0=0}$ and${\displaystyle a\cdot (b+c)=a\cdot b+a\cdot c}$.

Thecenter of a semiring is a sub-semiring and being commutative is equivalent to being its own center.

The commutative semiring of natural numbers is theinitial object among its kind, meaning there is a unique structure preserving map of${\displaystyle \mathbb{N}}$ into any commutative semiring.

The bounded distributive lattices arepartially ordered, commutative semirings fulfilling certain algebraic equations relating to distributivity and idempotence. Thus so are theirduals.

Notions or order can be defined using strict, non-strict orsecond-order formulations. Additional properties such as commutativity simplify the axioms.

Given astrict total order (also sometimes called linear order, orpseudo-order in a constructive formulation), then by definition, thepositive andnegative elements fulfill resp.. By irreflexivity of a strict order, if${\displaystyle s}$ is a left zero divisor, then is false. Thenon-negative elements are characterized by, which is then written${\displaystyle 0\le x}$.

Generally, the strict total order can be negated to define an associated partial order. Theasymmetry of the former manifests as. In fact inclassical mathematics the latter is a (non-strict) total order and such that${\displaystyle 0\le x}$ implies. Likewise, given any (non-strict) total order, its negation isirreflexive andtransitive, and those two properties found together are sometimes called strict quasi-order. Classically this defines a strict total order – indeed strict total order and total order can there be defined in terms of one another.

Recall that "${\displaystyle {\le }_{\text{pre}}}$" defined above is trivial in any ring. The existence of rings that admit a non-trivial non-strict order shows that these need not necessarily coincide with "${\displaystyle {\le }_{\text{pre}}}$".

A semiring in which every element is an additiveidempotent, that is,${\displaystyle x+x=x}$ for all elements${\displaystyle x}$, is called an(additively) idempotent semiring.^[9] Establishing${\displaystyle 1+1=1}$ suffices. Be aware that sometimes this is just called idempotent semiring, regardless of rules for multiplication.

In such a semiring,${\displaystyle x{\le }_{\text{pre}}y}$ is equivalent to${\displaystyle x+y=y}$ and always constitutes a partial order, here now denoted${\displaystyle x\le y}$. In particular, here${\displaystyle x\le 0\leftrightarrow x=0}$. So additively idempotent semirings are zerosumfree and, indeed, the only additively idempotent semiring that has all additive inverses is the trivial ring and so this property is specific to semiring theory. Addition and multiplication respect the ordering in the sense that${\displaystyle x\le y}$ implies${\displaystyle x+t\le y+t}$, and furthermore implies${\displaystyle s\cdot x\le s\cdot y}$ as well as${\displaystyle x\cdot s\le y\cdot s}$, for all${\displaystyle x,y,t}$ and${\displaystyle s}$.

If${\displaystyle R}$ is additively idempotent, then so are the polynomials in${\displaystyle R[X^{\ast }]}$.

A semiring such that there is a lattice structure on its underlying set islattice-ordered if the sum coincides with the meet,${\displaystyle x+y=x\vee y}$, and the product lies beneath the join${\displaystyle x\cdot y\le x\wedge y}$. The lattice-ordered semiring of ideals on a semiring is not necessarilydistributive with respect to the lattice structure.

More strictly than just additive idempotence, a semiring is calledsimple iff${\displaystyle x+1=1}$ for all${\displaystyle x}$. Then also${\displaystyle 1+1=1}$ and${\displaystyle x\le 1}$ for all${\displaystyle x}$. Here${\displaystyle 1}$ then functions akin to an additively infinite element. If${\displaystyle R}$ is an additively idempotent semiring, then${\displaystyle \{x\in R\mid x+1=1\}}$ with the inherited operations is its simple sub-semiring. An example of an additively idempotent semiring that is not simple is thetropical semiring on${\displaystyle \mathbb{R}\cup \{-\mathrm{\infty }\}}$ with the 2-ary maximum function, with respect to the standard order, as addition. Its simple sub-semiring is trivial.

Ac-semiring is an idempotent semiring and with addition defined over arbitrary sets.

An additively idempotent semiring with idempotent multiplication,${\displaystyle x^2=x}$, is calledadditively and multiplicatively idempotent semiring, but sometimes also just idempotent semiring. The commutative, simple semirings with that property are exactly the bounded distributive lattices with unique minimal and maximal element (which then are the units).Heyting algebras are such semirings and theBoolean algebras are a special case.

Further, given two bounded distributive lattices, there are constructions resulting in commutative additively-idempotent semirings, which are more complicated than just the direct sum of structures.

In a model of the ring${\displaystyle \mathbb{R}}$, one can define a non-trivial positivity predicate and a predicate as that constitutes a strict total order, which fulfills properties such as, or classically thelaw of trichotomy. With its standard addition and multiplication, this structure forms the strictlyordered field that isDedekind-complete.By definition, allfirst-order properties proven in the theory of the reals are also provable in thedecidable theory of thereal closed field. For example, here is mutually exclusive with${\displaystyle \mathrm{\exists }d.y+d^2=x}$.

But beyond just ordered fields, the four properties listed below are also still valid in many sub-semirings of${\displaystyle \mathbb{R}}$, including the rationals, the integers, as well as the non-negative parts of each of these structures. In particular, the non-negative reals, the non-negative rationals and the non-negative integers are such a semirings.The first two properties are analogous to the property valid in the idempotent semirings: Translation and scaling respect theseordered rings, in the sense that addition and multiplication in this ring validate

• 
• 

In particular, and so squaring of elements preserves positivity.

Take note of two more properties that are always valid in a ring. Firstly, trivially${\displaystyle P\to x{\le }_{\text{pre}}y}$ for any${\displaystyle P}$. In particular, thepositive additive difference existence can be expressed as

• 

Secondly, in the presence of a trichotomous order, the non-zero elements of the additive group are partitioned into positive and negative elements, with the inversion operation moving between them. With${\displaystyle (-1{)}^2=1}$, all squares are proven non-negative. Consequently, non-trivial rings have a positive multiplicative unit,

• 

Having discussed a strict order, it follows that${\displaystyle 0\ne 1}$ and${\displaystyle 1\ne 1+1}$, etc.

There are a few conflicting notions of discreteness in order theory. Given some strict order on a semiring, one such notion is given by${\displaystyle 1}$ being positive andcovering${\displaystyle 0}$, i.e. there being no element${\displaystyle x}$ between the units,. Now in the present context, an order shall be calleddiscrete if this is fulfilled and, furthermore, all elements of the semiring are non-negative, so that the semiring starts out with the units.

Denote by${\displaystyle {\mathsf{P}\mathsf{A}}^{-}}$ the theory of a commutative, discretely ordered semiring also validating the above four properties relating a strict order with the algebraic structure. All of its models have the model${\displaystyle \mathbb{N}}$ as its initial segment andGödel incompleteness andTarski undefinability already apply to${\displaystyle {\mathsf{P}\mathsf{A}}^{-}}$. The non-negative elements of a commutative,discretely ordered ring always validate the axioms of${\displaystyle {\mathsf{P}\mathsf{A}}^{-}}$. So a slightly more exotic model of the theory is given by the positive elements in thepolynomial ring${\displaystyle \mathbb{Z}[X]}$, with positivity predicate for${\displaystyle p={\sum }_{k=0}^n{a}_k{X}^k}$ defined in terms of the last non-zero coefficient,, and as above. While${\displaystyle {\mathsf{P}\mathsf{A}}^{-}}$ proves all${\displaystyle {\mathrm{\Sigma }}_1}$-sentences that are true about${\displaystyle \mathbb{N}}$, beyond this complexity one can find simple such statements that areindependent of${\displaystyle {\mathsf{P}\mathsf{A}}^{-}}$. For example, while${\displaystyle {\mathrm{\Pi }}_1}$-sentences true about${\displaystyle \mathbb{N}}$ are still true for the other model just defined, inspection of the polynomial${\displaystyle X}$ demonstrates${\displaystyle {\mathsf{P}\mathsf{A}}^{-}}$-independence of the${\displaystyle {\mathrm{\Pi }}_2}$-claim that all numbers are of the form${\displaystyle 2q}$ or${\displaystyle 2q+1}$ ("odd or even"). Showing that also${\displaystyle \mathbb{Z}[X,Y]/(X^2-2Y^2)}$ can be discretely ordered demonstrates that the${\displaystyle {\mathrm{\Pi }}_1}$-claim${\displaystyle x^2\ne 2y^2}$ for non-zero${\displaystyle x}$ ("no rational squared equals${\displaystyle 2}$") is independent. Likewise, analysis for${\displaystyle \mathbb{Z}[X,Y,Z]/(XZ-Y^2)}$ demonstrates independence of some statements aboutfactorization true in${\displaystyle \mathbb{N}}$. There are${\displaystyle \mathsf{P}\mathsf{A}}$ characterizations of primality that${\displaystyle {\mathsf{P}\mathsf{A}}^{-}}$ does not validate for the number${\displaystyle 2}$.

In the other direction, from any model of${\displaystyle {\mathsf{P}\mathsf{A}}^{-}}$ one may construct an ordered ring, which then has elements that are negative with respect to the order, that is still discrete the sense that${\displaystyle 1}$ covers${\displaystyle 0}$. To this end one defines an equivalence class of pairs from the original semiring. Roughly, the ring corresponds to the differences of elements in the old structure, generalizing the way in which theinitial ring${\displaystyle \mathbb{Z}}$can be defined from${\displaystyle \mathbb{N}}$. This, in effect, adds all the inverses and then the preorder is again trivial in that${\displaystyle \mathrm{\forall }x.x{\le }_{\text{pre}}0}$.

Beyond the size of the two-element algebra, no simple semiring starts out with the units. Being discretely ordered also stands in contrast to, e.g., the standard ordering on the semiring of non-negative rationals${\displaystyle {\mathbb{Q}}_{\ge 0}}$, which isdense between the units. For another example,${\displaystyle \mathbb{Z}[X]/(2X^2-1)}$ can be ordered, but not discretely so.

${\displaystyle {\mathsf{P}\mathsf{A}}^{-}}$ plusmathematical induction givesa theory equivalent to first-orderPeano arithmetic${\displaystyle \mathsf{P}\mathsf{A}}$. The theory is also famously notcategorical, but${\displaystyle \mathbb{N}}$ is of course the intended model.${\displaystyle \mathsf{P}\mathsf{A}}$ proves that there are no zero divisors and it is zerosumfree and so nomodel of it is a ring.

The standard axiomatization of${\displaystyle \mathsf{P}\mathsf{A}}$ is more concise and the theory of its order is commonly treated in terms of the non-strict "${\displaystyle {\le }_{\text{pre}}}$". However, just removing the potent induction principle from that axiomatization does not leave a workable algebraic theory. Indeed, evenRobinson arithmetic${\displaystyle \mathsf{Q}}$, which removes induction but adds back the predecessor existence postulate, does not prove the monoid axiom${\displaystyle \mathrm{\forall }y.(0+y=y)}$.

Acomplete semiring is a semiring for which the additive monoid is acomplete monoid, meaning that it has aninfinitary sum operation${\displaystyle {\mathrm{\Sigma }}_I}$ for anyindex set${\displaystyle I}$ and that the following (infinitary) distributive laws must hold:^[10][11][12]

${\displaystyle {\sum }_{i\in I}\left(a\cdot a_i\right)=a\cdot \left({\sum }_{i\in I}{a}_i\right),{\sum }_{i\in I}\left(a_i\cdot a\right)=\left({\sum }_{i\in I}{a}_i\right)\cdot a.}$

Examples of a complete semiring are the power set of a monoid under union and the matrix semiring over a complete semiring.^[13]For commutative, additively idempotent and simple semirings, this property is related toresiduated lattices.

Acontinuous semiring is similarly defined as one for which the addition monoid is acontinuous monoid. That is, partially ordered with theleast upper bound property, and for which addition and multiplication respect order and suprema. The semiring${\displaystyle \mathbb{N}\cup \{\mathrm{\infty }\}}$ with usual addition, multiplication and order extended is a continuous semiring.^[14]

Any continuous semiring is complete:^[10] this may be taken as part of the definition.^[13]

Astar semiring (sometimes spelledstarsemiring) orclosed semiring is a semiring with an additional unary operator${\displaystyle {}^{\ast }}$,^{[9][11][15][16]} satisfying

${\displaystyle a^{\ast }=1+a{a}^{\ast }=1+a^{\ast }a.}$

AKleene algebra is a star semiring with idempotent addition and some additional axioms. They are important in the theory offormal languages andregular expressions.^[11]

In acomplete star semiring, the star operator behaves more like the usualKleene star: for a complete semiring we use the infinitary sum operator to give the usual definition of the Kleene star:^[11]

${\displaystyle a^{\ast }={\sum }_{j\ge 0}{a}^j,}$

where

Note that star semirings are not related to*-algebra, where the star operation should instead be thought of ascomplex conjugation.

AConway semiring is a star semiring satisfying the sum-star and product-star equations:^[9][17]

Every complete star semiring is also a Conway semiring,^[18] but the converse does not hold. An example of Conway semiring that is not complete is the set of extended non-negativerational numbers${\displaystyle {\mathbb{Q}}_{\ge 0}\cup \{\mathrm{\infty }\}}$ with the usual addition and multiplication (this is a modification of the example with extended non-negative reals given in this section by eliminating irrational numbers).^[11]Aniteration semiring is a Conway semiring satisfying the Conway group axioms,^[9] associated byJohn Conway to groups in star-semirings.^[19]

• By definition, any ring and any semifield is also a semiring.
• The non-negative elements of a commutative, discretely ordered ring form a commutative, discretely (in the sense defined above) ordered semiring. This includes the non-negative integers${\displaystyle \mathbb{N}}$.
• Also the non-negativerational numbers as well as the non-negativereal numbers form commutative, ordered semirings.^[20][21][22] The latter is calledprobability semiring.^[6] Neither are rings or distributive lattices. These examples also have multiplicative inverses.
• New semirings can conditionally be constructed from existing ones, as described. Theextended natural numbers${\displaystyle \mathbb{N}\cup \{\mathrm{\infty }\}}$ with addition and multiplication extended so that${\displaystyle 0\cdot \mathrm{\infty }=0}$.^[21]
• The set ofpolynomials with natural number coefficients, denoted${\displaystyle \mathbb{N}[x],}$ forms a commutative semiring. In fact, this is thefree commutative semiring on a single generator${\displaystyle \{x\}.}$ Also polynomials with coefficients in other semirings may be defined, as discussed.
• The non-negativeterminating fractions${\displaystyle \frac{\mathbb{N}}{b^{\mathbb{N}}}:=\left\{m{b}^{-n}\mid m,n\in \mathbb{N}\right\}}$, in apositional number system to a given base${\displaystyle b\in \mathbb{N}}$, form a sub-semiring of the rationals. One has${\displaystyle \frac{\mathbb{N}}{b^{\mathbb{N}}}\subseteq \frac{\mathbb{N}}{c^{\mathbb{N}}}}$‍ if${\displaystyle b}$ divides${\displaystyle c}$. For${\displaystyle |b|>1}$, the set${\displaystyle \frac{{\mathbb{Z}}_0}{b^{{\mathbb{Z}}_0}}:=\frac{\mathbb{N}}{b^{\mathbb{N}}}\cup \left(-\frac{{\mathbb{N}}_0}{b^{\mathbb{N}}}\right)}$ is the ring of all terminating fractions to base${\displaystyle b,}$ and isdense in${\displaystyle \mathbb{Q}}$.
• Thelog semiring on${\displaystyle \mathbb{R}\cup \{\pm \mathrm{\infty }\}}$ with addition given by${\displaystyle x\oplus y=-\log \left(e^{-x}+e^{-y}\right)}$ with multiplication${\displaystyle +,}$ zero element${\displaystyle +\mathrm{\infty },}$ and unit element${\displaystyle 0.}$^[6]

Similarly, in the presence of an appropriate order with bottom element,

• Tropical semirings are variously defined. Themax-plus semiring${\displaystyle \mathbb{R}\cup \{-\mathrm{\infty }\}}$ is a commutative semiring with${\displaystyle max(a,b)}$ serving as semiring addition (identity${\displaystyle -\mathrm{\infty }}$) and ordinary addition (identity 0) serving as semiring multiplication. In an alternative formulation, the tropical semiring is${\displaystyle \mathbb{R}\cup \{\mathrm{\infty }\},}$ and min replaces max as the addition operation.^[23] A related version has${\displaystyle \mathbb{R}\cup \{\pm \mathrm{\infty }\}}$ as the underlying set.^[6][10] They are an active area of research, linkingalgebraic varieties withpiecewise linear structures.^[24]
• TheŁukasiewicz semiring: the closed interval${\displaystyle [0,1]}$ with addition of${\displaystyle a}$ and${\displaystyle b}$ given by taking the maximum of the arguments (${\displaystyle max(a,b)}$) and multiplication of${\displaystyle a}$ and${\displaystyle b}$ given by${\displaystyle max(0,a+b-1)}$ appears inmulti-valued logic.^[11]
• TheViterbi semiring is also defined over the base set${\displaystyle [0,1]}$ and has the maximum as its addition, but its multiplication is the usual multiplication of real numbers. It appears inprobabilistic parsing.^[11]

• The set of all ideals of a given semiring form a semiring under addition and multiplication of ideals.
• Any bounded, distributive lattice is a commutative, semiring under join and meet. A Boolean algebra is a special case of these. ABoolean ring is also a semiring (indeed, a ring) but it is not idempotent underaddition. ABoolean semiring is a semiring isomorphic to a sub-semiring of a Boolean algebra.^[20]
• The commutative semiring formed by the two-element Boolean algebra and defined by${\displaystyle 1+1=1}$. It is also calledtheBoolean semiring.^{[6][21][22][9]} Now given two sets${\displaystyle X}$ and${\displaystyle Y,}$binary relations between${\displaystyle X}$ and${\displaystyle Y}$ correspond to matrices indexed by${\displaystyle X}$ and${\displaystyle Y}$ with entries in the Boolean semiring,matrix addition corresponds to union of relations, andmatrix multiplication corresponds tocomposition of relations.^[25]
• Anyunital quantale is a semiring under join and multiplication.
• A normalskew lattice in a ring${\displaystyle R}$ is a semiring for the operations multiplication and nabla, where the latter operation is defined by${\displaystyle a\mathrm{\nabla }b=a+b+ba-aba-bab}$

More using monoids,

• The construction of semirings${\displaystyle \mathrm{End}(M)}$ from a commutative monoid${\displaystyle M}$ has been described. As noted, give a semiring${\displaystyle R}$, the${\displaystyle n\times n}$ matrices form another semiring. For example, the matrices with non-negative entries,${\displaystyle {\mathcal{M}}_n(\mathbb{N}),}$ form a matrix semiring.^[20]
• Given an alphabet (finite set) Σ, the set offormal languages over${\displaystyle \mathrm{\Sigma }}$ (subsets of${\displaystyle {\mathrm{\Sigma }}^{\ast }}$) is a semiring with product induced bystring concatenation${\displaystyle L_1\cdot L_2=\left\{w_1{w}_2\mid w_1\in L_1,w_2\in L_2\right\}}$ and addition as the union of languages (that is, ordinary union as sets). The zero of this semiring is the empty set (empty language) and the semiring's unit is the language containing only theempty string.^[11]
• Generalizing the previous example (by viewing${\displaystyle {\mathrm{\Sigma }}^{\ast }}$ as thefree monoid over${\displaystyle \mathrm{\Sigma }}$), take${\displaystyle M}$ to be any monoid; the power set${\displaystyle \mathrm{\wp }(M)}$ of all subsets of${\displaystyle M}$ forms a semiring under set-theoretic union as addition and set-wise multiplication:${\displaystyle U\cdot V=\{u\cdot v\mid u\in U,v\in V\}.}$^[22]
• Similarly, if${\displaystyle (M,e,\cdot )}$ is a monoid, then the set of finitemultisets in${\displaystyle M}$ forms a semiring. That is, an element is a function${\displaystyle f\mid M\to \mathbb{N}}$; given an element of${\displaystyle M,}$ the function tells you how many times that element occurs in the multiset it represents. The additive unit is the constant zero function. The multiplicative unit is the function mapping${\displaystyle e}$ to${\displaystyle 1,}$ and all other elements of${\displaystyle M}$ to${\displaystyle 0.}$ The sum is given by${\displaystyle (f+g)(x)=f(x)+g(x)}$ and the product is given by${\displaystyle (fg)(x)=\sum \{f(y)g(z)\mid y\cdot z=x\}.}$

Regarding sets and similar abstractions,

• Given a set${\displaystyle U,}$ the set ofbinary relations over${\displaystyle U}$ is a semiring with addition the union (of relations as sets) and multiplication thecomposition of relations. The semiring's zero is theempty relation and its unit is theidentity relation.^[11] These relations correspond to thematrix semiring (indeed, matrix semialgebra) ofsquare matrices indexed by${\displaystyle U}$ with entries in the Boolean semiring, and then addition and multiplication are the usual matrix operations, while zero and the unit are the usualzero matrix andidentity matrix.
• The set ofcardinal numbers smaller than any giveninfinite cardinal form a semiring under cardinal addition and multiplication. The class ofall cardinals of aninner model form a (class) semiring under (inner model) cardinal addition and multiplication.
• The family of (isomorphism equivalence classes of)combinatorial classes (sets of countably many objects with non-negative integer sizes such that there are finitely many objects of each size) with the empty class as the zero object, the class consisting only of the empty set as the unit,disjoint union of classes as addition, andCartesian product of classes as multiplication.^[26]
• Isomorphism classes of objects in anydistributive category, undercoproduct andproduct operations, form a semiring known as a Burnside rig.^[27] A Burnside rig is a ring if and only if the category istrivial.

Several structures mentioned above can be equipped with a star operation.

• Theaforementioned semiring ofbinary relations over some base set${\displaystyle U}$ in which${\displaystyle R^{\ast }=\bigcup _{n\ge 0}{R}^n}$ for all${\displaystyle R\subseteq U\times U.}$ This star operation is actually thereflexive andtransitive closure of${\displaystyle R}$ (that is, the smallest reflexive and transitive binary relation over${\displaystyle U}$ containing${\displaystyle R.}$).^[11]
• Thesemiring of formal languages is also a complete star semiring, with the star operation coinciding with the Kleene star (for sets/languages).^[11]
• The set of non-negativeextended reals${\displaystyle [0,\mathrm{\infty }]}$ together with the usual addition and multiplication of reals is a complete star semiring with the star operation given by${\displaystyle a^{\ast }=\frac{1}{1-a}}$ for (that is, thegeometric series) and${\displaystyle a^{\ast }=\mathrm{\infty }}$ for${\displaystyle a\ge 1.}$^[11]
• The Boolean semiring with${\displaystyle 0^{\ast }=1^{\ast }=1.}$^[b][11]
• The semiring on${\displaystyle \mathbb{N}\cup \{\mathrm{\infty }\},}$ with extended addition and multiplication, and${\displaystyle 0^{\ast }=1,a^{\ast }=\mathrm{\infty }}$ for${\displaystyle a\ge 1.}$^[b][11]

The${\displaystyle (max,+)}$ and${\displaystyle (min,+)}$tropical semirings on the reals are often used inperformance evaluation on discrete event systems. The real numbers then are the "costs" or "arrival time"; the "max" operation corresponds to having to wait for all prerequisites of an events (thus taking the maximal time) while the "min" operation corresponds to being able to choose the best, less costly choice; and + corresponds to accumulation along the same path.

TheFloyd–Warshall algorithm forshortest paths can thus be reformulated as a computation over a${\displaystyle (min,+)}$ algebra. Similarly, theViterbi algorithm for finding the most probable state sequence corresponding to an observation sequence in ahidden Markov model can also be formulated as a computation over a${\displaystyle (max,\times )}$ algebra on probabilities. Thesedynamic programming algorithms rely on thedistributive property of their associated semirings to compute quantities over a large (possibly exponential) number of terms more efficiently than enumerating each of them.^[28][29]

A generalization of semirings does not require the existence of a multiplicative identity, so that multiplication is asemigroup rather than a monoid. Such structures are calledhemirings^[30] orpre-semirings.^[31] A further generalization areleft-pre-semirings,^[32] which additionally do not require right-distributivity (orright-pre-semirings, which do not require left-distributivity).

Yet a further generalization arenear-semirings: in addition to not requiring a neutral element for product, or right-distributivity (or left-distributivity), they do not require addition to be commutative. Just as cardinal numbers form a (class) semiring, so doordinal numbers form anear-semiring, when the standardordinal addition and multiplication are taken into account. However, the class of ordinals can be turned into a semiring by considering the so-callednatural (or Hessenberg) operations instead.

Incategory theory, a2-rig is a category withfunctorial operations analogous to those of a rig. That the cardinal numbers form a rig can be categorified to say that thecategory of sets (or more generally, anytopos) is a 2-rig.

• Ring of sets – Family closed under unions and relative complements
• Valuation algebra – Algebra describing information processingPages displaying short descriptions of redirect targets

• Algebraic structures
• Ring theory

• CS1 French-language sources (fr)
• Articles with short description
• Short description is different from Wikidata
• Pages displaying short descriptions of redirect targets via Module:Annotated link
• CS1 maint: location