#jsDisabledContent { display:none; } My Account |  Register |  Help

# Semiring

Article Id: WHEBN0000371468
Reproduction Date:

 Title: Semiring Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

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

## Contents

• Definition 1
• Examples 2
• In general 2.1
• Specific examples 2.2
• Semiring theory 3
• Applications 4
• Complete and continuous semirings 5
• Star semirings 6
• Complete star semirings 6.1
• Further generalizations 7
• Semiring of sets 8
• Terminology 9
• Notes 11
• Bibliography 12

## Definition

A semiring is a set R equipped with two binary operations + and ·, called addition and multiplication, such that:[2][3][4]

1. (R, +) is a commutative monoid with identity element 0:
2. (a + b) + c = a + (b + c)
3. 0 + a = a + 0 = a
4. a + b = b + a
5. (R, ·) is a monoid with identity element 1:
6. (a·bc = a·(b·c)
7. a = a·1 = a
8. Multiplication left and right distributes over addition:
9. a·(b + c) = (a·b) + (a·c)
10. (a + bc = (a·c) + (b·c)
11. Multiplication by 0 annihilates R:
12. a = a·0 = 0
13. This last axiom is omitted from the definition of a ring: it follows from the other ring axioms. Here it does not, and it is necessary to state it in the definition.

The difference between rings and semirings, then, is that addition yields only a commutative monoid, not necessarily a commutative group. Specifically, elements in semirings do not necessarily have an inverse for the addition.

The symbol · is usually omitted from the notation; that is, a·b is just written ab. Similarly, an order of operations is accepted, according to which · is applied before +; that is, a + bc is a + (bc).

A commutative semiring is one whose multiplication is commutative.[5] An idempotent semiring is one whose addition is idempotent: a + a = a,[6] that is, (R, +, 0) is a join-semilattice with zero.

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]

## Examples

By definition, any ring is also a semiring. A motivating example of a semiring is the set of natural numbers N (including 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.[7][8][9]

### In general

• The set of all ideals of a given ring form a semiring under addition and multiplication of ideals.
• Any unital quantale is an idempotent semiring, or dioid, 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.[7]
• 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 a\nabla b=a+b+ba-aba-bab.
• Any c-semiring is also a semiring, where addition is idempotent and defined over arbitrary sets.

### Specific examples

• The extended natural numbers N∪{∞} with addition and multiplication extended (and 0⋅∞ = ∞).[8]
• The square n-by-n matrices with non-negative entries form a (not necessarily commutative) semiring under ordinary addition and multiplication of matrices. More generally, this likewise applies to the square matrices whose entries are elements of any other given semiring S, and this new semiring of matrices is generally non-commutative even though S may be commutative.[7]
• If A is a commutative monoid, the set End(A) of endomorphisms f:A→A form a semiring, where addition is pointwise addition and multiplication is function composition. The zero morphism and the identity are the respective neutral elements. If A is the additive monoid of natural numbers we obtain the semiring of natural numbers as End(A), and if A=S^n 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 Boolean semiring: the commutative semiring B formed by the two-element Boolean algebra and defined by 1+1=1:[3][8][9] this is idempotent[6] and is the simplest example of a semiring that is not a ring.
• N[x], polynomials with natural number coefficients form a commutative semiring. In fact, this is the free commutative semiring on a single generator {x}.
• Tropical semirings are variously defined. The max-plus semiring R ∪ {−∞}, is a commutative, idempotent semiring with 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 R ∪ {∞}, and min replaces max as the addition operation.[10] A related version has R ∪ {±∞} as the underlying set.[3][11]
• 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.[3]
• The log semiring on R ∪ ±∞ with addition given by
x \oplus y = - \log(e^{-x}+e^{-y}) \ ,
with multiplication +, zero element +∞ and unit element 0.[3]
• 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.[12]
• The Łukasiewicz semiring: the closed interval [0, 1] with addition given by taking the maximum of the arguments (a+b=max(a,b)) and multiplication ab given by max(0, a+b−1) appears in multi-valued logic.[13]
• The Viterbi semiring is also over the base set [0, 1] and addition by maximum, but with multiplication as the usual multiplication of reals; it appears in probabilistic parsing.[13]

• Given an alphabet (finite set) Σ, the set of formal languages over Σ (subsets of Σ*) is a semiring with product induced by string concatenation L_1 \cdot L_2 = \{w_1w_2 \mid w_1 \in L_1, w_2 \in L_2\} 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 as its sole element the empty string.[13]
• Generalising the previous example by viewing Σ 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: U \cdot V = \{ u \cdot v : u \in U,\ v \in v \}.[9]

## Semiring theory

Much of the theory of rings continues to make sense when applied to arbitrary semirings. In particular, one can generalise the theory of algebras over commutative rings directly to a theory of algebras over commutative semirings. Then a ring is simply an algebra over the commutative semiring Z of integers. Some mathematicians go so far as to say that semirings are really the more fundamental concept, and specialising to rings should be seen in the same light as specialising to, say, algebras over the complex numbers.

Idempotent semirings are special to semiring theory as any ring which is idempotent under addition is trivial. One can define a partial order ≤ on an idempotent semiring by setting ab whenever a + b = b (or, equivalently, if there exists an x such that a + x = b). It is easy to see that 0 is the least element with respect to this order: 0 ≤ a for all a. Addition and multiplication respect the ordering in the sense that ab implies acbc and cacb and (a+c) ≤ (b+c).

## Applications

Semirings, especially the (max, +) and (min, +) 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 (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 (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.

## Complete and continuous semirings

A complete semiring is a semiring for which the addition monoid is a complete monoid, meaning that it has an infinitary sum operation ΣI for any index set I and that the following (infinitary) distributive laws must hold:[11][13][14]

\sum_{i \in I}{(a \cdot a_i)} = a \cdot (\sum_{i \in I}{a_i}); \quad \sum_{i \in I}{(a_i \cdot a)} = (\sum_{i \in I}{a_i}) \cdot a.

Examples of complete semirings include the power set of a monoid under union; the matrix semiring over a complete semiring is complete.[15]

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 bounds property, and for which addition and multiplication respect order and suprema. The semiring N∪{∞} with usual addition, multiplication and order extended, is a continuous semiring.[16]

Any continuous semiring is complete:[11] this may be taken as part of the definition.[15]

## Star semirings

A star semiring (sometimes spelled as starsemiring) is a semiring with an additional unary operator *,[6][13][17][18] satisfying

a^* = 1 + aa^* = 1 + a^*a.\,

Examples of star semirings include:

• the (aforementioned) semiring of binary relations over some base set U in which R^* = \bigcup_{n \geq 0} R^n for all R\subseteq U \times U. This star operation is actually the reflexive and transitive closure of R (i.e. the smallest reflexive and transitive binary relation over U containing R.).[13]
• the semiring of formal languages is also a complete star semiring, with the star operation coinciding with the Kleene star (for sets/languages).[13]
• The set of non-negative extended reals, [0, ∞], together with the usual addition and multiplication of reals is a complete star semiring with the star operation given by a = 1/(1 − a) for 0 ≤ a < 1 (i.e. the geometric series) and a = ∞ for a ≥ 1.[13]

Further examples:[13]

• The Boolean semiring with 0 = 1 = 1;
• The semiring on N ∪ {∞}, with extended addition and multiplication, and 0 = 1, a = ∞ for a ≥ 1.

A Kleene algebra is a star semiring with idempotent addition: they are important in the theory of formal languages and regular expressions. A Conway semiring is a star semiring satisfying the sum-star and the product-star equations:[6][19]

(a+b)^* = (a^*b)^*a^*,\,
(ab)^* = 1 + a(ba)^*b.\,

The first three examples above are also Conway semirings.[13]

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

### Complete star semirings

We define a notion of complete star semiring in which 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:[13]

a^* = \sum_{j \geq 0}{a^j} where a^0 = 1 and a^{j+1} = a \cdot a^j = a^j \cdot a for j \geq 0

Examples of complete star semirings include the first three classes of examples in the previous section: the binary relations semiring; the formal languages semiring and the extended non-negative reals.[13]

In general, every complete star semiring is also a Conway semiring,[21] but the converse does not hold. An example of Conway semiring that is not complete is the set of extended non-negative rational numbers ({x ∈ Q | x ≥ 0} ∪ {∞}) 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).[13]

## Further generalizations

A near-ring does not require addition to be commutative, nor does it require right-distributivity. Just as cardinal numbers form a (class) semiring, so do ordinal numbers form a near-ring, 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.

## Semiring of sets

A semiring (of sets)[22] is a non-empty collection S of sets such that

1. \emptyset \in S
2. If E \in S and F \in S then E \cap F \in S.
3. If E \in S and F \in S then there exists a finite number of mutually disjoint sets C_i \in S for i=1,\ldots,n such that E \setminus F = \bigcup_{i=1}^n C_i.

Such semirings are used in measure theory. An example of a semiring of sets is the collection of half-open, half-closed real intervals [a,b) \subset \mathbb{R}.

## Terminology

The term dioid (for "double monoid") was used by Kuntzman in 1972 to denote what is now termed semiring.[23] The use to mean idempotent subgroup was introduced by Baccelli et al. in 1992.[24]

## Notes

1. ^ For an example see the definition of rig on Proofwiki.org

## Bibliography

1. ^ Głazek (2002) p.7
2. ^ Berstel & Perrin (1985), p. 26
3. ^ a b c d e Lothaire (2005) p.211
4. ^ Sakarovitch (2009) pp.27–28
5. ^ Lothaire (2005) p.212
6. ^ a b c d e Ésik, Zoltán (2008). "Iteration semirings". In Ito, Masami. Developments in language theory. 12th international conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Proceedings. Lecture Notes in Computer Science 5257. Berlin:
7. ^ a b c Guterman, Alexander E. (2008). "Rank and determinant functions for matrices over semirings". In Young, Nicholas; Choi, Yemon. Surveys in Contemporary Mathematics. London Mathematical Society Lecture Note Series 347.
8. ^ a b c Sakarovitch (2009) p.28
9. ^ a b c Berstel & Reutenauer (2011) p.4
10. ^ Speyer, David;
11. ^ a b c Kuich, Werner (2011). "Algebraic systems and pushdown automata". In Kuich, Werner. Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement. Lecture Notes in Computer Science 7020. Berlin:
12. ^ Bard, Gregory V. (2009), Algebraic Cryptanalysis, Springer, Section 4.2.1, "Combinatorial Classes", ff., pp. 30–34, .
13. ^ a b c d e f g h i j k l m n 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
14. ^ Kuich, Werner (1990). "ω-continuous semirings, algebraic systems and pushdown automata". In Paterson, Michael S. Automata, Languages and Programming: 17th International Colloquium, Warwick University, England, July 16-20, 1990, Proceedings. Lecture Notes in Computer Science 443.
15. ^ a b Sakaraovich (2009) p.471
16. ^ Ésik, Zoltán; Leiß, Hans (2002). "Greibach normal form in algebraically complete semirings". In Bradfield, Julian. 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 2471. Berlin:
17. ^ Lehmann, Daniel J. "Algebraic structures for transitive closure." Theoretical Computer Science 4, no. 1 (1977): 59-76.
18. ^ Berstel & Reutenauer (2011) p.27
19. ^ Ésik, Zoltán; Kuich, Werner (2004). "Equational axioms for a theory of automata". In Martín-Vide, Carlos. Formal languages and applications. Studies in Fuzziness and Soft Computing 148. Berlin:
20. ^
21. ^ 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
22. ^ Noel Vaillant, Caratheodory's Extension, on probability.net.
23. ^ Kuntzmann, J. (1972). Théorie des réseaux (graphes) (in French). Paris: Dunod.
24. ^ 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.
• 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, MR 1163371. Kluwer Academic Publishers, Dordrecht, 1999. xii+381 pp. ISBN 0-7923-5786-8 MR 1746739
• Berstel, Jean; Perrin, Dominique (1985). Theory of codes. Pure and applied mathematics 117. Academic Press.
• 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.
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge:
• Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications 137. Cambridge:

• Golan, Jonathan S. (2003). Semirings and Affine Equations over Them. Springer Science & Business Media.
• Gondran, Michel; Minoux, Michel (2008). Graphs, Dioids and Semirings: New Models and Algorithms. Operations Research/Computer Science Interfaces Series 41. Dordrecht: Springer Science & Business Media.
• Grillet, Mireille P. (1970). "Green’s relations in a semiring". Port. Math. 29: 181–195.
• Gunawardena, Jeremy (1998). "An introduction to idempotency". In Gunawardena, Jeremy. Idempotency. Based on a workshop, Bristol, UK, October 3–7, 1994 (PDF). Cambridge:
• Jipsen, P. (2004). "From semirings to residuated Kleene lattices". Studia Logica 76 (2): 291–303.
• Steven Dolan (2013) Fun with Semirings, doi:10.1145/2500365.2500613
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.

Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.