View source for Semiring

{{Short description|algebraic ring that need not have additive negative elements}}
In [[abstract algebra]], a '''semiring''' is an [[algebraic structure]] similar to a [[Ring (algebra)|ring]], but without the requirement that each element must have an [[additive inverse]].

The term '''rig''' is also used occasionally<ref>Głazek (2002) p.7</ref>—this originated as a joke, suggesting that rigs are ri''n''gs without ''n''egative elements, similar to using ''[[rng (algebra)|rng]]'' to mean a r''i''ng without a multiplicative ''i''dentity.

{{Algebraic structures |Ring}}

== Definition ==

A '''semiring''' is a [[Set (mathematics)|set]] ''R'' equipped with two [[binary operation]]s + and &sdot;, called addition and multiplication, such that:<ref>Berstel & Perrin (1985), [{{Google books|plainurl=y|id=GHJHqezwwpcC|page=26|text=a semiring K is a set equipped with two operations}} p. 26]</ref><ref name=LotIII211>Lothaire (2005) p.211</ref><ref name=Sak2728>Sakarovitch (2009) pp.27–28</ref>

* (''R'', +) is a [[commutative monoid]] with [[identity element]] 0:
** (''a'' + ''b'') + ''c'' = ''a'' + (''b'' + ''c'')
** 0 + ''a'' = ''a'' + 0 = ''a''
** ''a'' + ''b'' = ''b'' + ''a''
* (''R'', &sdot;) is a [[monoid]] with identity element 1:
** (''a''&sdot;''b'')&sdot;''c'' = ''a''&sdot;(''b''&sdot;''c'')
** 1&sdot;''a'' = ''a''&sdot;1 = ''a''
* Multiplication left and right [[distributive law|distributes]] over addition:
** ''a''&sdot;(''b'' + ''c'') = (''a''&sdot;''b'') + (''a''&sdot;''c'')
** (''a'' + ''b'')&sdot;''c'' = (''a''&sdot;''c'') + (''b''&sdot;''c'')
* Multiplication by 0 [[annihilating element|annihilates]] ''R'':
** 0&sdot;''a'' = ''a''&sdot;0 = 0

The symbol &sdot; is usually omitted from the notation; that is, ''a''&sdot;''b'' is just written ''ab''. Similarly, an [[order of operations]] is accepted, according to which &sdot; is applied before +; that is, {{nowrap|''a'' + ''bc''}} is {{nowrap|''a'' + (''bc'').}}

Compared to a [[ring (algebra)|ring]], a semiring omits the requirement for inverses under addition; that is, it requires only a [[commutative monoid]], not a [[commutative group]]. In a ring, this implies the existence of a multiplicative zero, so here it must be specified explicitly. If a semiring's multiplication is [[commutative]], then it is called a '''commutative semiring'''.<ref name=LotIII212>Lothaire (2005) p.212</ref>

There are some authors who prefer to leave out the requirement that a semiring have a 0 or 1. This makes the analogy between ''[[ring (algebra)|ring]]'' and ''semiring'' on the one hand and ''[[group (mathematics)|group]]'' and ''[[semigroup]]'' on the other hand work more smoothly. These authors often use ''rig'' for the concept defined here.<ref group="note">[http://www.proofwiki.org/wiki/Definition:Rig For an example see the definition of rig on Proofwiki.org]</ref>

== Theory ==

Much of the theory of rings continues to make sense when applied to arbitrary semirings{{citation needed|date=March 2015}}.
In particular, one can generalise the theory of (associative) [[algebra (ring theory)|algebras]] over [[commutative ring]]s directly to a theory of algebras over commutative semirings.
Then a ring is simply an algebra over the commutative semiring '''Z''' of [[integer]]s.

A semiring in which every element is an additive [[idempotent]] (that is, ''a'' + ''a'' = ''a'' for all elements ''a'') is called an '''{{visible anchor|idempotent semiring}}'''.<ref name=Esik08/> Idempotent semirings are special to semiring theory as any ring which is idempotent under addition is [[Trivial ring|trivial]].<ref group=note>i.e. is a ring consisting of just one element.</ref> One can define a [[partial order]] &le; on an idempotent semiring by setting {{nowrap|''a'' &le; ''b''}} whenever {{nowrap|1=''a'' + ''b'' = ''b''}} (or, equivalently, if there exists an ''x'' such that {{nowrap|1=''a'' + ''x'' = ''b''}}). It is easy to see that 0 is the [[least element]] with respect to this order: {{nowrap|0 &le; ''a''}} for all ''a''. Addition and multiplication respect the ordering in the sense that {{nowrap|''a'' &le; ''b''}} implies {{nowrap|''ac'' &le; ''bc''}} and {{nowrap|''ca'' &le; ''cb''}} and {{nowrap|(''a'' + ''c'') &le; (''b'' + ''c'')}}.

=== Applications ===

The {{nowrap|(max, +)}} and {{nowrap|(min, +)}} [[tropical semiring]]s on the reals, are often used in [[performance 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.

The [[Floyd–Warshall algorithm]] for [[shortest path]]s can thus be reformulated as a computation over a {{nowrap|(min, +)}} algebra.  Similarly, the [[Viterbi algorithm]] for finding the most probable state sequence corresponding to an observation sequence in a [[Hidden Markov model]] can also be formulated as a computation over a {{nowrap|(max, ×)}} algebra on probabilities.  These [[dynamic programming]] algorithms rely on the [[distributive property]] of their associated semirings to compute quantities over a large (possibly exponential) number of terms more efficiently than enumerating each of them.<ref name="Pair1966">
{{citation
 | first = Claude | last = Pair
 | chapter =  Sur des algorithmes pour des problèmes de cheminement dans les graphes finis (On algorithms for path problems in finite graphs)
 | title = Théorie des graphes (journées internationales d'études) -- Theory of Graphs (international symposium)
 | publisher = Dunod (Paris) et  Gordon and Breach (New York)
 | date = 1967
 | location = Rome (Italy), July 1966
 | page  = 271
 | editor = Rosentiehl
}}</ref><ref>
{{citation
 | first1 = Jean Claude | last1 = Derniame
 | first2 = Claude | last2 = Pair
 | title = Problèmes de cheminement dans les graphes (Path Problems in Graphs)
 | publisher = Dunod (Paris)
 | year = 1971
}}</ref>

== Examples ==

By definition, any ring is also a semiring. A motivating example of a semiring is the set of [[natural number]]s '''N''' (including [[0 (number)|zero]]) under ordinary addition and multiplication. Likewise, the non-negative [[rational number]]s and the non-negative [[real number]]s form semirings. All these semirings are commutative.<ref name=Gut08/><ref name=Sak28>Sakarovitch (2009) p.28</ref><ref name=BR4/>

===In general===
* The set of all [[ideal (ring theory)|ideals]] of a given ring form an idempotent semiring under addition and multiplication of ideals.
* Any [[quantale|unital quantale]] is an idempotent semiring under join and multiplication.
* Any bounded, [[distributive lattice]] is a commutative, idempotent semiring under join and meet.
* In particular, a [[Boolean algebra (structure)|Boolean algebra]] is such a semiring. A [[Boolean ring]] is also a semiring (indeed, a ring) but it is not idempotent under ''addition''.  A ''Boolean semiring'' is a semiring isomorphic to a subsemiring of a Boolean algebra.<ref name=Gut08>{{cite book | title=Surveys in Contemporary Mathematics | volume=347 | series=London Mathematical Society Lecture Note Series | issn=0076-0552 | editor1-first=Nicholas | editor1-last=Young | editor2-first=Yemon | editor2-last=Choi | publisher=[[Cambridge University Press]] | year=2008 | isbn=0-521-70564-9 | chapter=Rank and determinant functions for matrices over semirings | first=Alexander E. | last=Guterman | pages=1–33  | zbl=1181.16042 }}</ref>
* A normal [[skew lattice]] in a ring ''R'' is an idempotent semiring for the operations multiplication and nabla, where the latter operation is defined by <math>a\nabla b=a+b+ba-aba-bab</math>.
* Any [[c-semiring]] is also a semiring, where addition is idempotent and defined over arbitrary sets.
* Isomorphism classes of objects in any [[distributive category]], under [[coproduct]] and [[Product (category theory)|product]] operations, form a semiring known as a Burnside rig.<ref>Schanuel S.H. (1991) Negative sets have Euler characteristic and dimension. In: Carboni A., Pedicchio M.C., Rosolini G. (eds) Category Theory. Lecture Notes in Mathematics, vol 1488. Springer, Berlin, Heidelberg</ref> A Burnside rig is a ring if and only if the category is [[Category of small categories|trivial]].

==== Semiring of sets ====

A '''semiring''' ('''of sets''')<ref>Noel Vaillant, [http://www.probability.net/WEBcaratheodory.pdf Caratheodory's Extension], on probability.net.</ref> is a non-empty collection S of sets such that
# <math>\emptyset \in S</math>
# If <math>E \in S</math> and <math>F \in S</math> then <math>E \cap F \in S</math>.
# If <math>E \in S</math> and <math>F \in S</math> then there exists a finite number of mutually [[disjoint sets]] <math>C_i \in S</math> for <math>i=1,\ldots,n</math> such that <math>E \setminus F = \bigcup_{i=1}^n C_i</math>.

Such semirings are used in [[measure theory]]. An example of a semiring of sets is the collection of half-open, half-closed real [[interval (mathematics)|intervals]] <math>[a,b) \subset \mathbb{R}</math>.

===Specific examples===
{{unordered list
| The (non-negative) [[positional notation#Terminating fractions|''terminating fractions'']] <math>\frac{\N_0}{b^{\N_0}} := \left\{mb^{-n} \mid m, n \in \N_0 \right\}</math> in a [[positional notation|positional number system]] to a given base <math>b\in \N</math>. We have <math>\frac{\N_0}{b^{\N_0}} \subseteq \frac{\N_0}{c^{\N_0}}</math>{{zwj}} if <math>b</math> divides <math>c</math>. Furthermore, <math>\frac{\Z_0}{b^{\Z_0}} := \frac{\N_0}{b^{\N_0}} \cup \left(-\frac{\N_0}{b^{\N_0}}\right) </math> is the ring of all terminating fractions to base <math>b</math>, and is [[dense set|dense]] in <math>\Q</math> for <math>|b| > 1</math>.
| The extended natural numbers {{nowrap|'''N''' ∪ {∞}{{null}}}} with addition and multiplication extended (and {{nowrap|1=0⋅∞ = 0}}).<ref name=Sak28/>
| Given a semiring ''S'', the [[matrix semiring]] <math>M_n(S)</math> of the square ''n''-by-''n'' [[matrix (mathematics)|matrices]] form a semiring under ordinary [[Matrix addition|addition]] and [[matrix multiplication|multiplication]] of matrices, and this semiring of matrices is generally non-commutative even though ''S'' may be commutative. For example, the matrices with non-negative entries, <math>M_n(\N)</math>, form a matrix semiring.<ref name=Gut08/>
| If ''A'' is a commutative monoid, the set End(''A'') of [[endomorphism]]s {{nowrap|''f'' : ''A'' → ''A''}} almost forms a semiring, where addition is pointwise addition and multiplication is [[function composition]]. The [[zero morphism]] and the identity are the respective neutral elements. This is not a true semiring because composition does not distribute on the left over pointwise addition: {{nowrap|''a''{{Thin space}}·{{Thin space}}(''b''+''c'') ≠ (''a''·''b'') + (''a''·''c'')}}. If ''A'' is the additive monoid of natural numbers we obtain the semiring of natural numbers as End(''A''), and if {{nowrap|1=''A'' = ''S''<sup>''n''</sup>}} with ''S'' a semiring, we obtain (after associating each morphism to a matrix) the semiring of square ''n''-by-''n'' matrices with coefficients in ''S''.
| The '''{{visible anchor|Boolean semiring}}''' is the commutative semiring '''B''' formed by the [[two-element Boolean algebra]] and defined by {{nowrap|1=1 + 1 = 1}}.<ref name=LotIII211/><ref name=Sak28/><ref name=BR4>Berstel & Reutenauer (2011) p.&nbsp;4</ref> It is idempotent<ref name=Esik08/> and is the simplest example of a semiring that is not a ring. Given two sets ''X'' and ''Y'', [[binary relation]]s between ''X'' and ''Y'' correspond to matrices indexed by ''X'' and ''Y'' with entries in the Boolean semiring, [[matrix addition]] corresponds to union of relations, and [[matrix multiplication]] corresponds to [[composition of relations]].<ref>{{cite newsgroup |title=quantum mechanics over a commutative rig |author=[[John C. Baez]] |date=6 Nov 2001 |newsgroup=sci.physics.research |message-id=9s87n0$iv5@gap.cco.caltech.edu |url=https://groups.google.com/d/msg/sci.physics.research/VJNPMCfreao/TMKt9tFYNwEJ |access-date=November 25, 2018}}</ref>
| {{anchor|binary relations}}Given a set ''U'', the set of [[binary relation]]s over ''U'' is a semiring with addition the union (of relations as sets) and multiplication the [[composition of relations]]. The semiring's zero is the [[empty relation]] and its unit is the [[identity relation]].<ref name="droste"/> These relations correspond to the [[matrix semiring]] (indeed, matrix semialgebra) of [[square matrices]] indexed by ''U'' with entries in the Boolean semiring, and then addition and multiplication are the usual matrix operations, while zero and the unit are the usual [[zero matrix]] and [[identity matrix]].
| The set of [[polynomial]]s with natural number coefficients, denoted '''N'''[''x''], forms a commutative semiring. In fact, this is the [[free object|free]] commutative semiring on a single generator {''x''}.
| [[Tropical semiring]]s are variously defined.  The ''max-plus'' semiring '''R''' &cup; {−∞} is a commutative, idempotent semiring with {{nowrap|max(''a'', ''b'')}} serving as semiring addition (identity −∞) and ordinary addition (identity 0) serving as semiring multiplication.  In an alternative formulation, the tropical semiring is {{nowrap|'''R''' &cup; {∞},}} and min replaces max as the addition operation.<ref>{{cite journal |last=Speyer |first=David |last2=Sturmfels |first2=Bernd | author2-link=Bernd Sturmfels | arxiv=math/0408099 |title=Tropical Mathematics | origyear=2004 | year= 2009 | zbl=1227.14051 | journal=Math. Mag. | volume=82 | number=3 | pages=163–173 | doi=10.4169/193009809x468760}}</ref>  A related version has {{nowrap|'''R''' &cup; {±&infin;}{{null}}}} as the underlying set.<ref name=LotIII211/><ref name=Kuich11>{{cite book | last=Kuich | first=Werner | chapter=Algebraic systems and pushdown automata | zbl=1251.68135 | editor1-last=Kuich | editor1-first=Werner | title=Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement | location=Berlin | publisher=[[Springer-Verlag]] | isbn=978-3-642-24896-2 | series=Lecture Notes in Computer Science | volume=7020 | pages=228–256 | year=2011 }}</ref>
| The set of [[cardinal number]]s smaller than any given [[infinity|infinite]] cardinal form a semiring under cardinal addition and multiplication. The class of ''all cardinals'' of an [[inner model]] form a (class) semiring under (inner model) cardinal addition and multiplication.
| The '''{{visible anchor|probability semiring}}''' of non-negative real numbers under the usual addition and multiplication.<ref name=LotIII211/>
| The '''[[log semiring]]''' on '''R''' &cup; {±∞} with addition given by
: <math> x \oplus y = - \log(e^{-x}+e^{-y}) \ , </math>
with multiplication +, zero element +∞, and unit element 0.<ref name=LotIII211/>
| The family of (isomorphism equivalence classes of) [[combinatorial class]]es (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, and [[Cartesian product]] of classes as multiplication.<ref>{{citation|title=Algebraic Cryptanalysis|first=Gregory V.|last=Bard|publisher=Springer|year=2009|isbn=9780387887579|at=Section 4.2.1, "Combinatorial Classes", ff., pp. 30–34|url=https://books.google.com/books?id=kjbp0mgu3IAC&pg=PA30}}.</ref>
| The [[Jan Łukasiewicz|Łukasiewicz]] semiring: the closed interval {{nowrap|[0, 1]}} with addition given by taking the maximum of the arguments ({{nowrap|1=''a'' + ''b'' = max(''a'',''b'')}}) and multiplication ''ab'' given by {{nowrap|max(0, ''a'' + ''b'' − 1)}} appears in [[multi-valued logic]].<ref name="droste"/>
| The [[Andrew Viterbi|Viterbi]] semiring is also defined over the base set {{nowrap|[0, 1]}} and has the maximum as its addition, but its multiplication is the usual multiplication of real numbers. It appears in [[probabilistic parsing]].<ref name="droste"/>
| {{anchor|formal languages}}Given an alphabet (finite set) Σ, the set of [[formal language]]s over Σ (subsets of [[Kleene star|Σ<sup>&lowast;</sup>]]) is a semiring with product induced by [[string concatenation]] <math>L_1 \cdot L_2 = \left\{w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2\right\}</math> and addition as the union of languages (i.e. simply union as sets). The zero of this semiring is the empty set (empty language) and the semiring's unit is the language containing only the [[empty string]].<ref name="droste"/>
| Generalising the previous example (by viewing Σ<sup>&lowast;</sup> as the [[free monoid]] over Σ), take ''M'' to be any monoid; the power set '''P'''(''M'') of all subsets of ''M'' forms a semiring under set-theoretic union as addition and set-wise multiplication: <math>U \cdot V = \{ u \cdot v : u \in U,\ v \in V \}</math>.<ref name=BR4/>
| Similarly, if <math>(M, e, \cdot)</math> is a monoid, then the set of finite [[multiset]]s in <math>M</math> forms a semiring. That is, an element is a function <math>f : M \to \mathbb{N}</math>; given an element of <math>M</math>, 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 <math>e</math> to 1, and all other elements of <math>M</math> to 0. The sum is given by <math>(f + g)(x) = f(x) + g(x)</math> and the product is given by <math>(fg)(x) = \sum\{ f(y)g(z) \mid y \cdot z = x \}</math>.
}}

== Variations ==

=== Complete and continuous semirings ===
A '''complete semiring''' is a semiring for which the additive monoid is a [[complete monoid]], meaning that it has an [[Finitary|infinitary]] sum operation Σ<sub>''I''</sub> for any [[index set]] ''I'' and that the following (infinitary) distributive laws must hold:<ref name=Kuich11/><ref name="droste"/><ref>{{cite book | last=Kuich | first=Werner | chapter=ω-continuous semirings, algebraic systems and pushdown automata | pages=103–110 | title=Automata, Languages and Programming: 17th International Colloquium, Warwick University, England, July 16-20, 1990, Proceedings | volume=443 | series=Lecture Notes in Computer Science | editor1-first=Michael S. | editor1-last=Paterson | publisher=[[Springer-Verlag]] | year=1990 | isbn=3-540-52826-1 }}</ref>

: <math>\sum_{i \in I}{\left(a \cdot a_i\right)} = a \cdot \left(\sum_{i \in I}{a_i}\right), \qquad \sum_{i \in I}{\left(a_i \cdot a\right)} = \left(\sum_{i \in I}{a_i}\right) \cdot a.</math>

An examples of a complete semiring is the power set of a monoid under union. The matrix semiring over a complete semiring is complete.<ref name=Sak471/>

A '''continuous semiring''' is similarly defined as one for which the addition monoid is a [[continuous monoid]]. That is, partially ordered with the [[Least-upper-bound_property#Generalization_to_ordered_sets|least upper bound property]], and for which addition and multiplication respect order and suprema.  The semiring {{nowrap|'''N''' ∪ {∞}{{null}}}} with usual addition, multiplication and order extended is a continuous semiring.<ref>{{cite book | last1=Ésik | first1=Zoltán | last2=Leiß | first2=Hans | chapter=Greibach normal form in algebraically complete semirings | zbl=1020.68056 | editor1-last=Bradfield | editor1-first=Julian | title=Computer science logic. 16th international workshop, CSL 2002, 11th annual conference of the EACSL, Edinburgh, Scotland, September 22-25, 2002. Proceedings | location=Berlin | publisher=[[Springer-Verlag]] | series=Lecture Notes in Computer Science | volume=2471 | pages=135–150 | year=2002 }}</ref>

Any continuous semiring is complete:<ref name=Kuich11/> this may be taken as part of the definition.<ref name=Sak471>Sakaraovich (2009) p.471</ref>

=== Star semirings ===

A '''star semiring''' (sometimes spelled '''starsemiring''') is a semiring with an additional unary operator {{sup|&lowast;}},<ref name=Esik08/><ref name="droste">Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. ''Handbook of Weighted Automata'', 3–28. {{doi|10.1007/978-3-642-01492-5_1}}, pp. 7-10</ref><ref name=Lehmann>Lehmann, Daniel J. "Algebraic structures for transitive closure." ''Theoretical Computer Science'' 4, no. 1 (1977): 59-76.</ref><ref name=BR27>Berstel & Reutenauer (2011) p.27</ref> satisfying

:<math>a^* = 1 + aa^* = 1 + a^*a.</math>

A '''[[Kleene algebra]]''' is a star semiring with idempotent addition. They are important in the theory of [[formal language]]s and [[regular expression]]s.<ref name="droste"/>

==== Complete star semirings ====

In a '''complete star semiring''', the star operator behaves more like the usual [[Kleene star]]: for a complete semiring we use the infinitary sum operator to give the usual definition of the Kleene star:<ref name="droste"/>

: <math>a^* = \sum_{j \geq 0}{a^j} \mid a^j =
  \begin{cases}
    1,                                 & j = 0\\
    a \cdot a^{j-1} = a^{j-1} \cdot a, & j > 0
  \end{cases}
</math>

==== Conway semiring ====

A '''Conway semiring''' is a star semiring satisfying the sum-star and product-star equations:<ref name=Esik08/><ref>
{{cite book
 | last1=Ésik | first1=Zoltán
 | last2=Kuich | first2=Werner
 | chapter=Equational axioms for a theory of automata
 | editor1-last=Martín-Vide | editor1-first=Carlos
 | title=Formal languages and applications
 | location=Berlin
 | publisher=[[Springer-Verlag]]
 | series=Studies in Fuzziness and Soft Computing
 | volume=148 | pages=183–196
 | year=2004 | isbn=3-540-20907-7
 | zbl=1088.68117
}}</ref>
: <math>\begin{align}
  (a + b)^* &= \left(a^* b\right)^* a^*, \\
     (ab)^* &= 1 + a(ba)^* b.
\end{align}</math>

Every complete star semiring is also a Conway semiring,<ref name="droste15">Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. ''Handbook of Weighted Automata'', 3–28. {{doi|10.1007/978-3-642-01492-5_1}}, Theorem 3.4 p. 15</ref> but the converse does not hold. An example of Conway semiring that is not complete is the set of extended non-negative [[rational number]]s {{nowrap|'''Q'''<sub>≥0</sub> ∪ {∞}{{null}}}} 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).<ref name="droste"/>

An '''iteration semiring''' is a Conway semiring satisfying the Conway group axioms,<ref name=Esik08>{{cite book | last=Ésik | first=Zoltán | chapter=Iteration semirings | zbl=1161.68598 | editor1-last=Ito | editor1-first=Masami | title=Developments in language theory. 12th international conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Proceedings | location=Berlin | publisher=[[Springer-Verlag]] | isbn=978-3-540-85779-2 | series=Lecture Notes in Computer Science | volume=5257 | pages=1–20 | year=2008 | doi=10.1007/978-3-540-85780-8_1 }}</ref>  associated by [[John Horton Conway|John Conway]] to groups in star-semirings.<ref>{{cite book | first=J.H. | last=Conway | authorlink=John Horton Conway | title=Regular algebra and finite machines | publisher=Chapman and Hall | year=1971 | isbn=0-412-10620-5 | zbl=0231.94041 | location=London }}</ref>

==== Examples ====

Examples of star semirings include:
* the ([[#binary relations|aforementioned]]) semiring of [[binary relation]]s over some base set ''U'' in which <math>R^* = \bigcup_{n \geq 0} R^n</math> for all <math>R\subseteq U \times U</math>. This star operation is actually the [[Reflexive closure|reflexive]] and [[transitive closure]] of ''R'' (i.e. the smallest reflexive and transitive binary relation over ''U'' containing ''R''.).<ref name="droste"/>
* the [[#formal languages|semiring of formal languages]] is also a complete star semiring, with the star operation coinciding with the Kleene star (for sets/languages).<ref name="droste"/>
* The set of non-negative [[extended real]]s {{nowrap|[0, ∞]}} together with the usual addition and multiplication of reals is a complete star semiring with the star operation given by {{nowrap|1=''a''<sup>∗</sup> = 1/(1 − ''a'')}} for {{nowrap|0 ≤ ''a'' < 1}} (i.e. the [[geometric series]]) and {{nowrap|1=''a''<sup>∗</sup> = ∞}} for {{nowrap|''a'' ≥ 1}}.<ref name="droste"/>
* The Boolean semiring with {{nowrap|1=0<sup>&lowast;</sup> = 1<sup>&lowast;</sup> = 1}}.{{efn|name=conway|This is a complete star semiring and thus also a Conway semiring.<ref name="droste"/>}}<ref name="droste"/>
* The semiring on {{nowrap|'''N''' ∪ {∞},}} with extended addition and multiplication, and {{nowrap|1=0<sup>&lowast;</sup> = 1}}, {{nowrap|1=''a''<sup>&lowast;</sup> = ∞}} for {{nowrap|''a'' ≥ 1}}.{{efn|name=conway}}<ref name="droste"/>

{{noteslist}}

=== Dioid ===
The term '''dioid''' (for "double monoid") has been used to mean various types of semirings:
* It was used by Kuntzman in 1972 to denote what is now termed semiring.<ref>{{cite book | last=Kuntzmann | first=J. | title=Théorie des réseaux (graphes) | language=French | zbl=0239.05101 | location=Paris | publisher=Dunod | year=1972 }}</ref>
* The use to mean idempotent subgroup was introduced by Baccelli et al. in 1992.<ref>{{cite book | last1=Baccelli | first1=François Louis | last2=Olsder | first2=Geert Jan | last3=Quadrat | first3=Jean-Pierre | last4=Cohen | first4=Guy | title=Synchronization and linearity. An algebra for discrete event systems | zbl=0824.93003 | series=Wiley Series on Probability and Mathematical Statistics | location=Chichester | publisher=Wiley | year=1992 }}</ref>
* The name "dioid" is also sometimes used to denote [[naturally ordered semiring]]s.<ref>[http://marcpouly.ch/pdf/internal_100712.pdf Semirings for breakfast], slide 17</ref>

== Generalizations ==

A generalization of semirings does not require the existence of a multiplicative identity, so that multiplication is a [[semigroup]] rather than a monoid. Such structures are called ''hemirings''<ref>Jonathan S. Golan, ''Semirings and their applications'', Chapter 1, p1</ref> or ''pre-semirings''.<ref>Michel Gondran, Michel Minoux, ''Graphs, Dioids, and Semirings: New Models and Algorithms'', Chapter 1, Section 4.2, p22</ref> A further generalization are ''left-pre-semirings'',<ref>Michel Gondran, Michel Minoux, ''Graphs, Dioids, and Semirings: New Models and Algorithms'', Chapter 1, Section 4.1, p20</ref> which additionally do not require right-distributivity (or ''right-pre-semirings'', which do not require left-distributivity).

Yet a further generalization are ''[[near-semiring]]s'': 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 do [[ordinal number]]s form a [[near-ring]], when the standard [[Ordinal arithmetic|ordinal addition and multiplication]] are taken into account. However, the class of ordinals can be turned into a semiring by considering the so-called [[Ordinal arithmetic#Natural operations|natural (or Hessenberg) operations]] instead.

In [[category theory]], a ''2-rig'' is a category with [[functor]]ial operations analogous to those of a rig. That the cardinal numbers form a rig can be categorified to say that the [[category of sets]] (or more generally, any [[topos]]) is a 2-rig.

==See also==
*[[Ring of sets]]
*[[Valuation algebra]]

==Notes==
{{reflist|group=note}}

==Citations==
{{reflist|2}}

==Sources==
* {{citation | first1 = Jean Claude | last1 = Derniame| first2 = Claude | last2 = Pair| title = Problèmes de cheminement dans les graphes (Path Problems in Graphs)| publisher = Dunod (Paris)| year = 1971}}
* [[François Baccelli]], Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat, ''[http://cermics.enpc.fr/~cohen-g//SED/book-online.html Synchronization and Linearity (online version)]'', Wiley, 1992, {{isbn|0-471-93609-X}}
* Golan, Jonathan S., ''Semirings and their applications''. Updated and expanded version of ''The theory of semirings, with applications to mathematics and theoretical computer science'' (Longman Sci. Tech., Harlow, 1992, {{MathSciNet|id=1163371}}. Kluwer Academic Publishers, Dordrecht, 1999. xii+381 pp. {{isbn|0-7923-5786-8}} {{MathSciNet|id=1746739}}
* {{cite book |last1= Berstel |first1=Jean |authorlink1= |last2=Perrin |first2=Dominique |authorlink2= |title=Theory of codes |url= |edition= |series=Pure and applied mathematics |volume=117 |year=1985 |publisher=Academic Press |location= |isbn=978-0-12-093420-1 | zbl=0587.68066 }}
*{{cite book | last=Lothaire | first=M. | authorlink=M. Lothaire | title=Applied combinatorics on words | others=A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, [[Gesine Reinert]], Sophie Schbath, Michael Waterman, Philippe Jacquet, [[Wojciech Szpankowski]], Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and [[Valérie Berthé]]| series=Encyclopedia of Mathematics and Its Applications | volume=105 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2005 | isbn=0-521-84802-4 | zbl=1133.68067 }}
*{{cite book | last=Głazek | first=Kazimierz | title=A guide to the literature on semirings and their applications in mathematics and information sciences. With complete bibliography | location=Dordrecht | publisher=Kluwer Academic | year=2002 | isbn=1-4020-0717-5 | zbl=1072.16040 }}
* {{cite book | last=Sakarovitch | first=Jacques | title=Elements of automata theory | others=Translated from the French by Reuben Thomas | location=Cambridge | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-84425-3 | zbl=1188.68177 }}
* {{cite book | last1=Berstel | first1=Jean | last2=Reutenauer | first2=Christophe | title=Noncommutative rational series with applications | series=Encyclopedia of Mathematics and Its Applications | volume=137 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2011 | isbn=978-0-521-19022-0 | zbl=1250.68007 }}

==Further reading==
* {{cite book|first=Jonathan S. | last=Golan|title=Semirings and Affine Equations over Them|year=2003|publisher=Springer Science & Business Media|isbn=978-1-4020-1358-4 | zbl=1042.16038}}
* {{cite book|first1=Michel | last1=Gondran| first2=Michel | last2=Minoux | title=Graphs, Dioids and Semirings: New Models and Algorithms | year=2008 | location=Dordrecht | publisher=Springer Science & Business Media|isbn=978-0-387-75450-5 | zbl=1201.16038 | series=Operations Research/Computer Science Interfaces Series | volume=41}}
* {{cite journal | last=Grillet | first=Mireille P. | title=Green’s relations in a semiring | zbl=0227.16029 | journal=Port. Math. | volume=29 | pages=181–195 | year=1970 | url=https://eudml.org/doc/115127 }}
* {{cite book | last=Gunawardena | first=Jeremy | chapter=An introduction to idempotency | zbl=0898.16032 | editor1-last=Gunawardena | editor1-first=Jeremy | title=Idempotency. Based on a workshop, Bristol, UK, October 3–7, 1994 | location=Cambridge | publisher=[[Cambridge University Press]] | pages=1–49 | year=1998 | url=http://www.hpl.hp.com/techreports/96/HPL-BRIMS-96-24.pdf }}
* {{cite journal | first=P. | last=Jipsen | title=From semirings to residuated Kleene lattices | journal=Studia Logica | volume=76 | number=2 | year=2004 | pages=291–303 | zbl=1045.03049 | doi=10.1023/B:STUD.0000032089.54776.63 }}
* Steven Dolan (2013) [http://www.cl.cam.ac.uk/~sd601/papers/semirings.pdf Fun with Semirings], {{doi|10.1145/2500365.2500613}}

[[Category:Algebraic structures]]
[[Category:Ring theory]]