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 te ...
, 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 ...
similar to a
ring, but without the requirement that each element must have an
additive inverse.
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 semiring
In idempotent analysis, the tropical semiring is a semiring of extended real numbers with the operations of minimum (or maximum) and addition replacing the usual ("classical") operations of addition and multiplication, respectively.
The tropic ...
s are an active area of research, linking
algebraic varieties
Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex number
...
with
piecewise linear structures.
Definition
A semiring is a
set 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
called addition and multiplication, such that:
[Lothaire (2005) p.211][Sakarovitch (2009) pp.27–28]
*
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 s ...
:
**
**
**
*
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.
Monoids ...
with identity element
:
**
**
* Multiplication left and right
distributes over addition:
**
**
* Multiplication by
annihilates :
**
The symbol
is usually omitted from the notation; that is,
is just written
Similarly, an
order of operations is conventional, in which
is applied before
; that is,
is
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.
[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](_blank)
/ref>
Theory
One can generalize the theory of (associative) algebras over commutative rings directly to a theory of algebras over commutative semirings.
A semiring in which every element is an additive idempotent (that is, for all elements ) is called an .[ Idempotent semirings are specific to semiring theory since any idempotent semiring that is also a ring is in fact trivial.][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 ...
on an idempotent semiring by setting whenever (or, equivalently, if there exists an such that ). The least element with respect to this order is meaning that for all Addition and multiplication respect the ordering in the sense that implies and and
Applications
The and tropical semiring
In idempotent analysis, the tropical semiring is a semiring of extended real numbers with the operations of minimum (or maximum) and addition replacing the usual ("classical") operations of addition and multiplication, respectively.
The tropic ...
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
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between t ...
s can thus be reformulated as a computation over a 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 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.[
]
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 (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 measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s form semirings. All these semirings are commutative.[Sakarovitch (2009) p.28][
]
In general
* The set of all ideals
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considered ...
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
In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set ...
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 ...
is such a semiring. A Boolean ring 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 is an idempotent semiring for the operations multiplication and nabla, where the latter operation is defined by
* 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.
Semiring of sets
A (of sets) is a (non-empty) collection of subsets of such that
-
* If (3) holds, then if and only if
- If then
- If 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. ...
such that
Conditions (2) and (3) together with imply that 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 or is a collection of subsets of satisfying the semiring properties except with (3) replaced with:
* If 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. ...
such that
This condition is stronger than (3), which can be seen as follows. If is a semialgebra and , then we can write for disjoint . Then:
and every since it is closed under intersection, and disjoint since they are contained in the disjoint 's. Moreover the condition is ''strictly'' stronger: any 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 ).
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 for any index set and that the following (infinitary) distributive laws must hold:
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
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.
Monoids ar ...
. That is, partially ordered with the least upper bound property, and for which addition and multiplication respect order and suprema. The semiring 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-10][Lehmann, Daniel J. "Algebraic structures for transitive closure." ''Theoretical Computer Science'' 4, no. 1 (1977): 59-76.][Berstel & Reutenauer (2011) p.27] satisfying
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 s ...
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:
where
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:[
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 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 Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
s over some base set in which for all This star operation is actually the reflexive and transitive closure of (that is, the smallest reflexive and transitive binary relation over containing ).
* 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