HOME

TheInfoList



OR:

In
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The ter ...
, a semiring is an
algebraic structure In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set o ...
similar to a ring, but without the requirement that each element must have an
additive inverse In mathematics, the additive inverse of a number is the number that, when added to , yields zero. This number is also known as the opposite (number), sign change, and negation. For a real number, it reverses its sign: the additive inverse (op ...
. The term rig is also used occasionally—this originated as a joke, suggesting that rigs are ri''n''gs without ''n''egative elements, similar to using '' rng'' to mean a r''i''ng without a multiplicative ''i''dentity. Tropical semirings are an active area of research, linking algebraic varieties with piecewise linear structures.


Definition

A semiring is a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
R equipped with two
binary operation In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary op ...
s \,+\, and \,\cdot,\, called addition and multiplication, such that:Lothaire (2005) p.211Sakarovitch (2009) pp.27–28 * (R, +) is a commutative monoid with
identity element In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
0: ** (a + b) + c = a + (b + c) ** 0 + a = a = a + 0 ** a + b = b + a * (R, \,\cdot\,) is a
monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoid ...
with identity element 1: ** (a \cdot b) \cdot c = a \cdot (b \cdot c) ** 1 \cdot a = a = a \cdot 1 * Multiplication left and right distributes over addition: ** a \cdot (b + c) = (a \cdot b) + (a \cdot c) ** (a + b) \cdot c = (a \cdot c) + (b \cdot c) * Multiplication by 0 annihilates R: ** 0 \cdot a = 0 = a \cdot 0 The symbol \cdot is usually omitted from the notation; that is, a \cdot b is just written ab. Similarly, an
order of operations In mathematics and computer programming, the order of operations (or operator precedence) is a collection of rules that reflect conventions about which procedures to perform first in order to evaluate a given mathematical expression. For examp ...
is conventional, in which \,\cdot\, is applied before \,+\,; that is, a + b c is a + (b c). 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 In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
, then it is called a commutative semiring.Lothaire (2005) p.212 There are some authors who prefer to leave out the requirement that a semiring have a 0 or 1. This makes the analogy between and on the one hand and and on the other hand work more smoothly. These authors often use for the concept defined here.For an example see the definition of rig on Proofwiki.org
/ref>


Theory

One can generalize the theory of (associative) algebras over
commutative ring In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not ...
s directly to a theory of algebras over commutative semirings. A semiring in which every element is an additive
idempotent Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
(that is, a + a = a for all elements a) is called an . Idempotent semirings are specific to semiring theory since any idempotent semiring that is also a ring is in fact
trivial Trivia is information and data that are considered to be of little value. It can be contrasted with general knowledge and common sense. Latin Etymology The ancient Romans used the word ''triviae'' to describe where one road split or fork ...
.i.e. is a ring consisting of just one element, because rings have additive inverses, unlike semirings. One can define a
partial order In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
\,\leq\, on an idempotent semiring by setting a \leq b whenever a + b = b (or, equivalently, if there exists an x such that a + x = b). The least element with respect to this order is 0, meaning that 0 \leq a for all a. Addition and multiplication respect the ordering in the sense that a \leq b implies a c \leq b c and c a \leq c b and (a + c) \leq (b + c).


Applications

The (\max, +) and (\min, +) tropical semirings on the reals are often used in
performance evaluation A performance appraisal, also referred to as a performance review, performance evaluation,Muchinsky, P. M. (2012). ''Psychology Applied to Work'' (10th ed.). Summerfield, NC: Hypergraphic Press. (career) development discussion, or employee appr ...
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 In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with ...
for shortest paths can thus be reformulated as a computation over a (\min, +) algebra. Similarly, the
Viterbi algorithm The Viterbi algorithm is a dynamic programming algorithm for obtaining the maximum a posteriori probability estimate of the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events, especiall ...
for finding the most probable state sequence corresponding to an observation sequence in a
hidden Markov model A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process — call it X — with unobservable ("''hidden''") states. As part of the definition, HMM requires that there be an ...
can also be formulated as a computation over a (\max, \times) algebra on probabilities. These
dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
algorithms rely on the
distributive property In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmet ...
of their associated semirings to compute quantities over a large (possibly exponential) number of terms more efficiently than enumerating each of them.


Examples

By definition, any ring is also a semiring. A motivating example of a semiring is the set of
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
s \N (including the number zero) under ordinary addition and multiplication. Likewise, the non-negative
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
s and the non-negative
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s form semirings. All these semirings are commutative.Sakarovitch (2009) p.28


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 In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
is such a semiring. A
Boolean ring In mathematics, a Boolean ring ''R'' is a ring for which ''x''2 = ''x'' for all ''x'' in ''R'', that is, a ring that consists only of idempotent elements. An example is the ring of integers modulo 2. Every Boolean ring gives rise to a Boolean al ...
is also a semiring (indeed, a ring) but it is not idempotent under . A is a semiring isomorphic to a subsemiring of a Boolean algebra. * A normal
skew lattice In abstract algebra, a skew lattice is an algebraic structure that is a non-commutative generalization of a lattice. While the term ''skew lattice'' can be used to refer to any non-commutative generalization of a lattice, since 1989 it has been use ...
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. * Isomorphism classes of objects in any distributive category, under coproduct and product operations, form a semiring known as a Burnside rig. A Burnside rig is a ring if and only if the category is
trivial Trivia is information and data that are considered to be of little value. It can be contrasted with general knowledge and common sense. Latin Etymology The ancient Romans used the word ''triviae'' to describe where one road split or fork ...
.


Semiring of sets

A (of sets) is a (non-empty) collection \mathcal of subsets of X such that
  1. \varnothing \in \mathcal. * If (3) holds, then \varnothing \in \mathcal if and only if \mathcal \neq \varnothing.
  2. If E, F \in \mathcal then E \cap F \in \mathcal.
  3. If E, F \in \mathcal then there exists a finite number of mutually
    disjoint sets In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...
    C_1, \ldots, C_n \in \mathcal such that E \setminus F = \bigcup_^n C_i.
Conditions (2) and (3) together with S \neq \varnothing imply that \varnothing \in S. Such semirings are used in
measure theory In mathematics, the concept of a measure is a generalization and formalization of geometrical measures (length, area, volume) and other common notions, such as mass and probability of events. These seemingly distinct concepts have many simila ...
. An example of a semiring of sets is the collection of half-open, half-closed real intervals [a, b) \subset \R. A or is a collection \mathcal of subsets of X satisfying the semiring properties except with (3) replaced with: * If E \in \mathcal then there exists a finite number of mutually
disjoint sets In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...
C_1, \ldots, C_n \in \mathcal such that X \setminus E = \bigcup_^n C_i. This condition is stronger than (3), which can be seen as follows. If \mathcal is a semialgebra and E, F \in \mathcal, then we can write F^c = F_1 \cup ... \cup F_n for disjoint F_i \in S. Then: 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 E \cap F_i \in S since it is closed under intersection, and disjoint since they are contained in the disjoint F_i's. Moreover the condition is ''strictly'' stronger: any 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 X).


Specific examples


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 \Sigma_I for any index set I and that the following (infinitary) distributive laws must hold: \sum_ = a \cdot \left(\sum_\right), \qquad \sum_ = \left(\sum_\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. 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 \N \cup \ with usual addition, multiplication and order extended is a continuous semiring. Any continuous semiring is complete: this may be taken as part of the definition.Sakaraovich (2009) p.471


Star semirings

A star semiring (sometimes spelled starsemiring) is a semiring with an additional unary operator ,Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. ''Handbook of Weighted Automata'', 3–28. , pp. 7-10Lehmann, Daniel J. "Algebraic structures for transitive closure." ''Theoretical Computer Science'' 4, no. 1 (1977): 59-76.Berstel & Reutenauer (2011) p.27 satisfying a^* = 1 + a a^* = 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 language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sym ...
s and
regular expression A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" ...
s.


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: a^* = \sum_, where a^j = \begin 1, & j = 0,\\ a \cdot a^ = a^ \cdot a, & j > 0. \end Note that star semirings are not related to *-algebra, where the star operation should instead be thought of as
complex conjugation In mathematics, the complex conjugate of a complex number is the number with an equal real part and an imaginary part equal in magnitude but opposite in sign. That is, (if a and b are real, then) the complex conjugate of a + bi is equal to a - ...
.


Conway semiring

A Conway semiring is a star semiring satisfying the sum-star and product-star equations: \begin (a + b)^* &= \left(a^* b\right)^* a^*, \\ (ab)^* &= 1 + a(ba)^* b. \end Every complete star semiring is also a Conway semiring,Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. ''Handbook of Weighted Automata'', 3–28. , Theorem 3.4 p. 15 but the converse does not hold. An example of Conway semiring that is not complete is the set of extended non-negative
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
s \Q_ \cup \ 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). An iteration semiring is a Conway semiring satisfying the Conway group axioms, associated by John Conway to groups in star-semirings.


Examples

Examples of star semirings include: * the ( aforementioned) semiring of
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
s over some base set U in which R^* = \bigcup_ R^n for all R\subseteq U \times U. This star operation is actually the reflexive and transitive closure of R (that is, the smallest reflexive and transitive binary relation over U containing R.). * the semiring of formal languages is also a complete star semiring, with the star operation coinciding with the Kleene star (for sets/languages). * The set of non-negative extended reals , \infty/math> together with the usual addition and multiplication of reals is a complete star semiring with the star operation given by a^* = \frac for 0 \leq a < 1 (that is, the
geometric series In mathematics, a geometric series is the sum of an infinite number of terms that have a constant ratio between successive terms. For example, the series :\frac \,+\, \frac \,+\, \frac \,+\, \frac \,+\, \cdots is geometric, because each suc ...
) and a^* = \infty for a \geq 1. * The Boolean semiring with 0^* = 1^* = 1. * The semiring on \N \cup \, with extended addition and multiplication, and 0^* = 1, a^* = \infty for a \geq 1.


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


Generalizations

A generalization of semirings does not require the existence of a multiplicative identity, so that multiplication is a
semigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
rather than a monoid. Such structures are called or . A further generalization are ,Michel Gondran, Michel Minoux, ''Graphs, Dioids, and Semirings: New Models and Algorithms'', Chapter 1, Section 4.1, p20 which additionally do not require right-distributivity (or , which do not require left-distributivity). Yet a further generalization are : 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 In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the leas ...
s form a
near-semiring In mathematics, a near-semiring (also ''seminearring'') is an algebraic structure more general than a near-ring or a semiring. Near-semirings arise naturally from functions on monoids. Definition A near-semiring is a set ''S'' with two bina ...
, 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 Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
, a is a category with
functor In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
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 In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition o ...
(or more generally, any
topos In mathematics, a topos (, ; plural topoi or , or toposes) is a category that behaves like the category of sheaves of sets on a topological space (or more generally: on a site). Topoi behave much like the category of sets and possess a notio ...
) is a 2-rig.


See also

* *


Notes


Citations


Bibliography

* *
François Baccelli François Louis Baccelli (born December 20, 1954) is senior researcher at INRIA Paris, in charge of the ERC project NEMO on network mathematics. Education and career Baccelli obtained his PhD at the University of Paris-Sud in 1983 under the super ...
, Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat,
Synchronization and Linearity (online version)
', Wiley, 1992, * 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, . Kluwer Academic Publishers, Dordrecht, 1999. xii+381 pp. * * * * * *


Further reading

* * * * * * Steven Dolan (2013
Fun with Semirings
{{Authority control Algebraic structures Ring theory