Semiring

In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse.

The term rig is also used occasionally^[1]—this originated as a joke, suggesting that rigs are rings without negative elements, similar to using rng to mean a ring without a multiplicative identity.

Tropical semirings are an active area of research, linking algebraic varieties with piecewise linear structures.^[2]

Definition

A semiring is a set ${\displaystyle R}$  equipped with two binary operations ${\displaystyle \,+\,}$  and ${\displaystyle \,\cdot ,\,}$  called addition and multiplication, such that:^[3][4][5]

• ${\displaystyle (R,+)}$  is a commutative monoid with identity element ${\displaystyle 0}$ :
  • ${\displaystyle (a+b)+c=a+(b+c)}$ 
  • ${\displaystyle 0+a=a=a+0}$ 
  • ${\displaystyle a+b=b+a}$ 
• ${\displaystyle (R,\,\cdot \,)}$  is a monoid with identity element ${\displaystyle 1}$ :
  • ${\displaystyle (a\cdot b)\cdot c=a\cdot (b\cdot c)}$ 
  • ${\displaystyle 1\cdot a=a=a\cdot 1}$ 
• Multiplication left and right distributes over addition:
  • ${\displaystyle a\cdot (b+c)=(a\cdot b)+(a\cdot c)}$ 
  • ${\displaystyle (a+b)\cdot c=(a\cdot c)+(b\cdot c)}$ 
• Multiplication by ${\displaystyle 0}$  annihilates ${\displaystyle R}$ :
  • ${\displaystyle 0\cdot a=0=a\cdot 0}$ 

The symbol ${\displaystyle \cdot }$  is usually omitted from the notation; that is, ${\displaystyle a\cdot b}$  is just written ${\displaystyle ab.}$  Similarly, an order of operations is conventional, in which ${\displaystyle \,\cdot \,}$  is applied before ${\displaystyle \,+\,}$ ; that is, ${\displaystyle a+bc}$  is ${\displaystyle a+(bc).}$ 

Compared to a 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, the additive inverse requirement 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.^[6]

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 and semiring on the one hand and group and semigroup on the other hand work more smoothly. These authors often use rig for the concept defined here.^{[note 1]}

Theory

One can generalize the theory of (associative) algebras over commutative rings directly to a theory of algebras over commutative semirings.^{[citation needed]}

A semiring in which every element is an additive idempotent (that is, ${\displaystyle a+a=a}$  for all elements ${\displaystyle a}$ ) is called an idempotent semiring.^[7] Idempotent semirings are specific to semiring theory since any idempotent semiring that is also a ring is in fact trivial.^{[note 2]} One can define a partial order ${\displaystyle \,\leq \,}$  on an idempotent semiring by setting ${\displaystyle a\leq b}$  whenever ${\displaystyle a+b=b}$  (or, equivalently, if there exists an ${\displaystyle x}$  such that ${\displaystyle a+x=b}$ ). The least element with respect to this order is ${\displaystyle 0,}$  meaning that ${\displaystyle 0\leq a}$  for all ${\displaystyle a.}$  Addition and multiplication respect the ordering in the sense that ${\displaystyle a\leq b}$  implies ${\displaystyle ac\leq bc}$  and ${\displaystyle ca\leq cb}$  and ${\displaystyle (a+c)\leq (b+c).}$ 

Applications

The ${\displaystyle (\max ,+)}$  and ${\displaystyle (\min ,+)}$  tropical semirings 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 paths can thus be reformulated as a computation over a ${\displaystyle (\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 ${\displaystyle (\max ,\times )}$  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.^[8][9]

Examples

By definition, any ring is also a semiring. A motivating example of a semiring is the set of natural numbers ${\displaystyle \mathbb {N} }$  (including the number zero) under ordinary addition and multiplication. Likewise, the non-negative rational numbers and the non-negative real numbers form semirings. All these semirings are commutative.^[10][11][12]

In general

• The set of all ideals of a given ring form an idempotent semiring under addition and multiplication of ideals.
• Any 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 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.^[10]
• A normal skew lattice in a ring ${\displaystyle R}$  is an idempotent semiring for the operations multiplication and nabla, where the latter operation is defined by ${\displaystyle a\nabla b=a+b+ba-aba-bab.}$ 
• 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 operations, form a semiring known as a Burnside rig.^[13] A Burnside rig is a ring if and only if the category is trivial.

Semiring of sets

See also: Ring of sets § semiring

A semiring (of sets)^[14] is a (non-empty) collection ${\displaystyle {\mathcal {S}}}$  of subsets of ${\displaystyle X}$  such that

1. ${\displaystyle \varnothing \in {\mathcal {S}}.}$ 
   • If (3) holds, then ${\displaystyle \varnothing \in {\mathcal {S}}}$  if and only if ${\displaystyle {\mathcal {S}}\neq \varnothing .}$ 
2. If ${\displaystyle E,F\in {\mathcal {S}}}$  then ${\displaystyle E\cap F\in {\mathcal {S}}.}$ 
3. If ${\displaystyle E,F\in {\mathcal {S}}}$  then there exists a finite number of mutually disjoint sets ${\displaystyle C_{1},\ldots ,C_{n}\in {\mathcal {S}}}$  such that ${\displaystyle E\setminus F=\bigcup _{i=1}^{n}C_{i}.}$ 

Conditions (2) and (3) together with ${\displaystyle S\neq \varnothing }$  imply that ${\displaystyle \varnothing \in S.}$  Such semirings are used in measure theory. An example of a semiring of sets is the collection of half-open, half-closed real intervals ${\displaystyle [a,b)\subset \mathbb {R} .}$ 

A semialgebra^[15] or elementary family ^[16] is a collection ${\displaystyle {\mathcal {S}}}$  of subsets of ${\displaystyle X}$  satisfying the semiring properties except with (3) replaced with:

• If ${\displaystyle E\in {\mathcal {S}}}$  then there exists a finite number of mutually disjoint sets ${\displaystyle C_{1},\ldots ,C_{n}\in {\mathcal {S}}}$  such that ${\displaystyle X\setminus E=\bigcup _{i=1}^{n}C_{i}.}$ 

This condition is stronger than (3), which can be seen as follows. If ${\displaystyle {\mathcal {S}}}$  is a semialgebra and ${\displaystyle E,F\in {\mathcal {S}}}$ , then we can write ${\displaystyle F^{c}=F_{1}\cup ...\cup F_{n}}$  for disjoint ${\displaystyle F_{i}\in S}$ . Then:

$${\displaystyle E\setminus F=E\cap F^{c}=E\cap (F_{1}\cup ...\cup F_{n})=(E\cap F_{1})\cup ...\cup (E\cap F_{n})}$$

 

and every ${\displaystyle E\cap F_{i}\in S}$  since it is closed under intersection, and disjoint since they are contained in the disjoint ${\displaystyle F_{i}}$ 's. Moreover the condition is strictly stronger: any ${\displaystyle S}$  that is both a ring and a semialgebra is an algebra, hence any ring that is not an algebra is also not a semialgebra (e.g. the collection of finite sets on an infinite set ${\displaystyle X}$ ).

Specific examples

• The (non-negative) terminating fractions ${\displaystyle {\frac {\mathbb {N} _{0}}{b^{\mathbb {N} _{0}}}}:=\left\{mb^{-n}:m,n\in \mathbb {N} _{0}\right\}}$  in a positional number system to a given base ${\displaystyle b\in \mathbb {N} .}$  We have ${\displaystyle {\frac {\mathbb {N} _{0}}{b^{\mathbb {N} _{0}}}}\subseteq {\frac {\mathbb {N} _{0}}{c^{\mathbb {N} _{0}}}}}$ ‍ if ${\displaystyle b}$  divides ${\displaystyle c.}$  Furthermore, ${\displaystyle {\frac {\mathbb {Z} _{0}}{b^{\mathbb {Z} _{0}}}}:={\frac {\mathbb {N} _{0}}{b^{\mathbb {N} _{0}}}}\cup \left(-{\frac {\mathbb {N} _{0}}{b^{\mathbb {N} _{0}}}}\right)}$  is the ring of all terminating fractions to base ${\displaystyle b,}$  and is dense in ${\displaystyle \mathbb {Q} }$  for ${\displaystyle |b|>1.}$ 
• The extended natural numbers ${\displaystyle \mathbb {N} \cup \{\infty \}}$  with addition and multiplication extended (and ${\displaystyle 0\cdot \infty =0}$ ).^[11]
• Given a semiring ${\displaystyle S,}$  the matrix semiring ${\displaystyle M_{n}(S)}$  of the square ${\displaystyle n{\text{ by }}n}$  matrices form a semiring under ordinary addition and multiplication of matrices, and this semiring of matrices is generally non-commutative even though ${\displaystyle S}$  may be commutative. For example, the matrices with non-negative entries, ${\displaystyle M_{n}(\mathbb {N} ),}$  form a matrix semiring.^[10]
• If ${\displaystyle A}$  is a commutative monoid, the set ${\displaystyle \operatorname {End} (A)}$  of endomorphisms ${\displaystyle f:A\to A}$  forms a semiring, where addition is pointwise addition and multiplication is function composition. The zero morphism and the identity are the respective neutral elements. If ${\displaystyle A}$  is the additive monoid of natural numbers we obtain the semiring of natural numbers as ${\displaystyle \operatorname {End} (A),}$  if ${\displaystyle A=S^{n}}$  with ${\displaystyle S}$  a semiring, we obtain (after associating each morphism to a matrix) the semiring of square ${\displaystyle n{\text{ by }}n}$  matrices with coefficients in ${\displaystyle S,}$  and if ${\displaystyle A}$  is a (commutative) group, then ${\displaystyle \operatorname {End} (A)}$  is a (not necessarily commutative) ring.
• The Boolean semiring is the commutative semiring ${\displaystyle \mathbf {B} }$  formed by the two-element Boolean algebra and defined by ${\displaystyle 1+1=1.}$ ^[4][11][12] It is idempotent^[7] and is the simplest example of a semiring that is not a ring. 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, and matrix multiplication corresponds to composition of relations.^[17]
• Given a set ${\displaystyle U,}$  the set of binary relations over ${\displaystyle 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.^[18] These relations correspond to the matrix semiring (indeed, matrix semialgebra) of square 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 usual zero matrix and identity matrix.
• The set of polynomials with natural number coefficients, denoted ${\displaystyle \mathbb {N} [x],}$  forms a commutative semiring. In fact, this is the free commutative semiring on a single generator ${\displaystyle \{x\}.}$ 
• Tropical semirings are variously defined. The max-plus semiring ${\displaystyle \mathbb {R} \cup \{-\infty \}}$ is a commutative, idempotent semiring with ${\displaystyle \max(a,b)}$  serving as semiring addition (identity ${\displaystyle -\infty }$ ) and ordinary addition (identity 0) serving as semiring multiplication. In an alternative formulation, the tropical semiring is ${\displaystyle \mathbb {R} \cup \{\infty \},}$  and min replaces max as the addition operation.^[19] A related version has ${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$  as the underlying set.^[4][20]
• The set of cardinal numbers smaller than any given 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 probability semiring of non-negative real numbers under the usual addition and multiplication.^[4]
• The log semiring on ${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$  with addition given by
  $${\displaystyle x\oplus y=-\log \left(e^{-x}+e^{-y}\right)}$$

   
  with multiplication ${\displaystyle \,+,\,}$  zero element ${\displaystyle +\infty ,}$  and unit element ${\displaystyle 0.}$ ^[4]
• 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, and Cartesian product of classes as multiplication.^[21]
• The Łukasiewicz semiring: the closed interval ${\displaystyle [0,1]}$  with addition given by taking the maximum of the arguments (${\displaystyle a+b=\max(a,b)}$ ) and multiplication ${\displaystyle ab}$  given by ${\displaystyle \max(0,a+b-1)}$  appears in multi-valued logic.^[18]
• The Viterbi 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 in probabilistic parsing.^[18]
• Given an alphabet (finite set) Σ, the set of formal languages over ${\displaystyle \Sigma }$  (subsets of ${\displaystyle \Sigma ^{*}}$ ) is a semiring with product induced by string concatenation ${\displaystyle L_{1}\cdot L_{2}=\left\{w_{1}w_{2}: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 the empty string.^[18]
• Generalizing the previous example (by viewing ${\displaystyle \Sigma ^{*}}$  as the free monoid over ${\displaystyle \Sigma }$ ), take ${\displaystyle M}$  to be any monoid; the power set ${\displaystyle \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:u\in U,\ v\in V\}.}$ ^[12]
• Similarly, if ${\displaystyle (M,e,\cdot )}$  is a monoid, then the set of finite multisets in ${\displaystyle M}$  forms a semiring. That is, an element is a function ${\displaystyle f: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):y\cdot z=x\}.}$ 

^[2]

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 infinitary sum operation ${\displaystyle \Sigma _{I}}$  for any index set ${\displaystyle I}$  and that the following (infinitary) distributive laws must hold:^[20][18][22]

$${\displaystyle \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.}$$

 

Examples of a complete semiring are the power set of a monoid under union and the matrix semiring over a complete semiring.^[23]

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, and for which addition and multiplication respect order and suprema. The semiring ${\displaystyle \mathbb {N} \cup \{\infty \}}$  with usual addition, multiplication and order extended is a continuous semiring.^[24]

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

Star semirings

A star semiring (sometimes spelled starsemiring) is a semiring with an additional unary operator ^∗,^{[7][18][25][26]} satisfying

$${\displaystyle a^{*}=1+aa^{*}=1+a^{*}a.}$$

 

A Kleene algebra is a star semiring with idempotent addition and some additional axioms. They are important in the theory of formal languages and regular expressions.^[18]

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:^[18]

$${\displaystyle a^{*}=\sum _{j\geq 0}{a^{j}},}$$

 

where ${\displaystyle a^{j}={\begin{cases}1,&j=0,\\a\cdot a^{j-1}=a^{j-1}\cdot a,&j>0.\end{cases}}}$ 

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

Conway semiring

A Conway semiring is a star semiring satisfying the sum-star and product-star equations:^[7][27]

$${\displaystyle {\begin{aligned}(a+b)^{*}&=\left(a^{*}b\right)^{*}a^{*},\\(ab)^{*}&=1+a(ba)^{*}b.\end{aligned}}}$$

 

Every complete star semiring is also a Conway semiring,^[28] but the converse does not hold. An example of Conway semiring that is not complete is the set of extended non-negative rational numbers ${\displaystyle \mathbb {Q} _{\geq 0}\cup \{\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).^[18]

An iteration semiring is a Conway semiring satisfying the Conway group axioms,^[7] associated by John Conway to groups in star-semirings.^[29]

Examples

Examples of star semirings include:

• the (aforementioned) semiring of binary relations over some base set ${\displaystyle U}$  in which ${\displaystyle R^{*}=\bigcup _{n\geq 0}R^{n}}$  for all ${\displaystyle R\subseteq U\times U.}$  This star operation is actually the reflexive and transitive closure of ${\displaystyle R}$  (that is, the smallest reflexive and transitive binary relation over ${\displaystyle U}$  containing ${\displaystyle R.}$ ).^[18]
• the semiring of formal languages is also a complete star semiring, with the star operation coinciding with the Kleene star (for sets/languages).^[18]
• The set of non-negative extended reals ${\displaystyle [0,\infty ]}$  together with the usual addition and multiplication of reals is a complete star semiring with the star operation given by ${\displaystyle a^{*}={\frac {1}{1-a}}}$  for ${\displaystyle 0\leq a<1}$  (that is, the geometric series) and ${\displaystyle a^{*}=\infty }$  for ${\displaystyle a\geq 1.}$ ^[18]
• The Boolean semiring with ${\displaystyle 0^{*}=1^{*}=1.}$ ^[a][18]
• The semiring on ${\displaystyle \mathbb {N} \cup \{\infty \},}$  with extended addition and multiplication, and ${\displaystyle 0^{*}=1,a^{*}=\infty }$  for ${\displaystyle a\geq 1.}$ ^[a][18]

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.^[30]
• The use to mean idempotent subgroup was introduced by Baccelli et al. in 1992.^[31]
• The name "dioid" is also sometimes used to denote naturally ordered semirings.^[32]

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^[33] or pre-semirings.^[34] A further generalization are left-pre-semirings,^[35] which additionally do not require right-distributivity (or right-pre-semirings, which do not require left-distributivity).

Yet a further generalization are near-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 do ordinal numbers form a near-semiring, when the standard ordinal addition and multiplication are taken into account. However, the class of ordinals can be turned into a semiring by considering the so-called natural (or Hessenberg) operations instead.

In category theory, a 2-rig is a category with functorial 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 – Family closed under unions and relative complements
• Valuation algebra

Notes

1. For an example see the definition of rig on Proofwiki.org
2. i.e. is a ring consisting of just one element, because rings have additive inverses, unlike semirings.

1. This is a complete star semiring and thus also a Conway semiring.^[18]

Citations

1. Głazek (2002) p.7
2. Speyer, David; Sturmfels, Bernd (2009). "Tropical Mathematics". Mathematics Magazine. 82 (3): 163–173. doi:10.1080/0025570X.2009.11953615. ISSN 0025-570X. S2CID 15278805.
3. Berstel & Perrin (1985), p. 26
4. Lothaire (2005) p.211
5. Sakarovitch (2009) pp.27–28
6. Lothaire (2005) p.212
7. Ésik, Zoltán (2008). "Iteration semirings". In Ito, Masami (ed.). Developments in language theory. 12th international conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Proceedings. Lecture Notes in Computer Science. Vol. 5257. Berlin: Springer-Verlag. pp. 1–20. doi:10.1007/978-3-540-85780-8_1. ISBN 978-3-540-85779-2. Zbl 1161.68598.
8. Pair, Claude (1967), "Sur des algorithmes pour des problèmes de cheminement dans les graphes finis (On algorithms for path problems in finite graphs)", in Rosentiehl (ed.), Théorie des graphes (journées internationales d'études) -- Theory of Graphs (international symposium), Rome (Italy), July 1966: Dunod (Paris) et Gordon and Breach (New York), p. 271{{citation}}: CS1 maint: location (link)
9. Derniame, Jean Claude; Pair, Claude (1971), Problèmes de cheminement dans les graphes (Path Problems in Graphs), Dunod (Paris)
10. Guterman, Alexander E. (2008). "Rank and determinant functions for matrices over semirings". In Young, Nicholas; Choi, Yemon (eds.). Surveys in Contemporary Mathematics. London Mathematical Society Lecture Note Series. Vol. 347. Cambridge University Press. pp. 1–33. ISBN 978-0-521-70564-6. ISSN 0076-0552. Zbl 1181.16042.
11. Sakarovitch (2009) p.28
12. Berstel & Reutenauer (2011) p. 4
13. 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
14. Noel Vaillant, Caratheodory's Extension, on probability.net.
15. Durrett 2019, pp. 3–4. sfn error: no target: CITEREFDurrett2019 (help)
16. Folland 1999, p. 23. sfn error: no target: CITEREFFolland1999 (help)
17. John C. Baez (6 Nov 2001). "quantum mechanics over a commutative rig". Newsgroup: sci.physics.research. Usenet: 9s87n0$[e-mail]. Retrieved November 25, 2018.
18. 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
19. Speyer, David; Sturmfels, Bernd (2009) [2004]. "Tropical Mathematics". Math. Mag. 82 (3): 163–173. arXiv:math/0408099. doi:10.4169/193009809x468760. S2CID 119142649. Zbl 1227.14051.
20. Kuich, Werner (2011). "Algebraic systems and pushdown automata". In Kuich, Werner (ed.). Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement. Lecture Notes in Computer Science. Vol. 7020. Berlin: Springer-Verlag. pp. 228–256. ISBN 978-3-642-24896-2. Zbl 1251.68135.
21. Bard, Gregory V. (2009), Algebraic Cryptanalysis, Springer, Section 4.2.1, "Combinatorial Classes", ff., pp. 30–34, ISBN 9780387887579.
22. Kuich, Werner (1990). "ω-continuous semirings, algebraic systems and pushdown automata". In Paterson, Michael S. (ed.). Automata, Languages and Programming: 17th International Colloquium, Warwick University, England, July 16-20, 1990, Proceedings. Lecture Notes in Computer Science. Vol. 443. Springer-Verlag. pp. 103–110. ISBN 3-540-52826-1.
23. Sakaraovich (2009) p.471
24. Ésik, Zoltán; Leiß, Hans (2002). "Greibach normal form in algebraically complete semirings". In Bradfield, Julian (ed.). Computer science logic. 16th international workshop, CSL 2002, 11th annual conference of the EACSL, Edinburgh, Scotland, September 22-25, 2002. Proceedings. Lecture Notes in Computer Science. Vol. 2471. Berlin: Springer-Verlag. pp. 135–150. Zbl 1020.68056.
25. Lehmann, Daniel J. "Algebraic structures for transitive closure." Theoretical Computer Science 4, no. 1 (1977): 59-76.
26. Berstel & Reutenauer (2011) p.27
27. Ésik, Zoltán; Kuich, Werner (2004). "Equational axioms for a theory of automata". In Martín-Vide, Carlos (ed.). Formal languages and applications. Studies in Fuzziness and Soft Computing. Vol. 148. Berlin: Springer-Verlag. pp. 183–196. ISBN 3-540-20907-7. Zbl 1088.68117.
28. 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
29. Conway, J.H. (1971). Regular algebra and finite machines. London: Chapman and Hall. ISBN 0-412-10620-5. Zbl 0231.94041.
30. Kuntzmann, J. (1972). Théorie des réseaux (graphes) (in French). Paris: Dunod. Zbl 0239.05101.
31. Baccelli, François Louis; Olsder, Geert Jan; Quadrat, Jean-Pierre; Cohen, Guy (1992). Synchronization and linearity. An algebra for discrete event systems. Wiley Series on Probability and Mathematical Statistics. Chichester: Wiley. Zbl 0824.93003.
32. Semirings for breakfast, slide 17
33. Jonathan S. Golan, Semirings and their applications, Chapter 1, p1
34. Michel Gondran, Michel Minoux, Graphs, Dioids, and Semirings: New Models and Algorithms, Chapter 1, Section 4.2, p22
35. Michel Gondran, Michel Minoux, Graphs, Dioids, and Semirings: New Models and Algorithms, Chapter 1, Section 4.1, p20

Bibliography

• Derniame, Jean Claude; Pair, Claude (1971), Problèmes de cheminement dans les graphes (Path Problems in Graphs), Dunod (Paris)
• François Baccelli, Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat, 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, MR1163371. Kluwer Academic Publishers, Dordrecht, 1999. xii+381 pp. ISBN 0-7923-5786-8 MR1746739
• Berstel, Jean; Perrin, Dominique (1985). Theory of codes. Pure and applied mathematics. Vol. 117. Academic Press. ISBN 978-0-12-093420-1. Zbl 0587.68066.
• Durrett, Richard (2019). Probability: Theory and Examples (PDF). Cambridge Series in Statistical and Probabilistic Mathematics. Vol. 49 (5th ed.). Cambridge New York, NY: Cambridge University Press. ISBN 978-1-108-47368-2. OCLC 1100115281. Retrieved November 5, 2020.
• Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 105. 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é. Cambridge: Cambridge University Press. ISBN 0-521-84802-4. Zbl 1133.68067.
• Głazek, Kazimierz (2002). A guide to the literature on semirings and their applications in mathematics and information sciences. With complete bibliography. Dordrecht: Kluwer Academic. ISBN 1-4020-0717-5. Zbl 1072.16040.
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
• Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. Vol. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.

Further reading

• Golan, Jonathan S. (2003). Semirings and Affine Equations over Them. Springer Science & Business Media. ISBN 978-1-4020-1358-4. Zbl 1042.16038.
• Gondran, Michel; Minoux, Michel (2008). Graphs, Dioids and Semirings: New Models and Algorithms. Operations Research/Computer Science Interfaces Series. Vol. 41. Dordrecht: Springer Science & Business Media. ISBN 978-0-387-75450-5. Zbl 1201.16038.
• Grillet, Mireille P. (1970). "Green's relations in a semiring". Port. Math. 29: 181–195. Zbl 0227.16029.
• Gunawardena, Jeremy (1998). "An introduction to idempotency". In Gunawardena, Jeremy (ed.). Idempotency. Based on a workshop, Bristol, UK, October 3–7, 1994 (PDF). Cambridge: Cambridge University Press. pp. 1–49. Zbl 0898.16032.
• Jipsen, P. (2004). "From semirings to residuated Kleene lattices". Studia Logica. 76 (2): 291–303. doi:10.1023/B:STUD.0000032089.54776.63. S2CID 9946523. Zbl 1045.03049.
• Steven Dolan (2013) Fun with Semirings, doi:10.1145/2500365.2500613