Semiring

A semiring is an algebraic structure consisting of a nonempty set S equipped with two binary operations: addition and multiplication. It also has two distinguished elements, 0 and 1, which serve as additive and multiplicative identities, respectively. The addition operation is associative and commutative, the multiplication is associative, multiplication distributes over addition on both sides, and multiplication by 0 yields 0. Unlike rings, semirings do not require additive inverses.

Typical examples include the natural numbers with ordinary addition and multiplication, the set of nonnegative real numbers, and the Boolean semiring with OR as addition and AND as multiplication. The tropical semiring uses min (or max) for addition and ordinary addition for multiplication. Matrices over a semiring form a semiring under standard matrix addition and multiplication.

Commutative semirings have commutative multiplication. A semiring is idempotent if a + a = a for all elements a. Many semirings may have zero divisors and a zero that is absorbing for multiplication. Subsemirings and semiring homomorphisms—maps that preserve both operations and send 0 to 0 and 1 to 1—are common notions in the theory.

Semirings support various constructions, such as polynomial and power series semirings, and function semirings. They play a central role in automata theory and formal languages, where addition models union and multiplication models concatenation. The tropical semiring, in particular, is used in optimization and shortest-path problems, while other semirings model weighted sums or costs in diverse computational settings.