Complete Star 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—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 $R$ equipped with two binary operations $\,+\,$ and $\,\cdot,\,$ called addition and multiplication, such that:Lothaire (2005) p.211Sakarovitch (2009) pp.27–28

* $(R, +)$ is a commutative monoid with identity element $0$:
** $(a + b) + c = a + (b + c)$
** $0 + a = a = a + 0$
** $a + b = b + a$
* $(R, \,\cdot\,)$ is a 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 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, 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 rings directly to a theory of algebras over commutative semirings.

A semiring in which every element is an additive idempotent (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.i.e. is a ring consisting of just one element, because rings have additive inverses, unlike semirings. One can define a partial order $\,\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 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, \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.

Examples

By definition, any ring is also a semiring. A motivating example of a semiring is the set of natural numbers $\N$ (including the 0 (number), 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.Sakarovitch (2009) p.28

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 . A is a semiring isomorphic to a subsemiring of a Boolean algebra.
* 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.
* Isomorphism classes of objects in any distributive category, under coproduct and Product (category theory), product operations, form a semiring known as a Burnside rig. A Burnside rig is a ring if and only if the category is Category of small categories, trivial.

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 $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. An example of a semiring of sets is the collection of half-open, half-closed real Interval (mathematics), 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 $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#Generalization to ordered sets, 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 languages and regular expressions.

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.

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 numbers $\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 Horton Conway, John Conway to groups in star-semirings.

Examples

Examples of star semirings include:
* the (#binary relations, aforementioned) semiring of binary relations 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 closure, reflexive and transitive closure of $R$ (that is, the smallest reflexive and transitive binary relation over $U$ containing $R.$).
* 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).
* The set of non-negative extended reals $[0, \infty]$ 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) 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 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 numbers form a near-semiring, 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 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

*
*

Notes

Citations

Bibliography

*
* François Baccelli, 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