Fact-checked by Grok 2 weeks ago

Semiring

A semiring is an algebraic structure consisting of a set S equipped with two binary operations, addition (denoted +) and multiplication (denoted \cdot), such that (S, +) is a commutative monoid with identity element $0, (S, \cdot) is a monoid with identity element $1, multiplication distributes over addition on both sides (i.e., a \cdot (b + c) = a \cdot b + a \cdot c and (a + b) \cdot c = a \cdot c + b \cdot c for all a, b, c \in S), and [0](/page/0) acts as an absorbing element for multiplication (i.e., a \cdot 0 = 0 \cdot a = 0 for all a \in S).^[1] Semirings generalize rings by relaxing the requirement for additive inverses, allowing for structures where subtraction is not always possible, such as the natural numbers under usual addition and multiplication.^[1] The concept was formally introduced by H. S. Vandiver in 1934 as a "simple type of algebra" lacking the cancellation law for addition, motivated by studies in ring ideals and finite arithmetics. Common examples include the semiring of non-negative integers (\mathbb{N}_0, +, \cdot, 0, 1), the Boolean semiring (\{0,1\}, \lor, \land, 0, 1) used in logic, and the max-plus semiring (\mathbb{R} \cup \{\infty\}, \max, +, \infty, 0) applied in optimization problems.^[1] Semirings play a central role in various mathematical and computational domains, including formal language theory where they model weighted automata, idempotent analysis for solving nonlinear equations without inverses, and tropical geometry as an algebraic framework for optimization and polyhedral computations.^[1] Their theory encompasses ideals, homomorphisms, and radicals analogous to ring theory; semirings are also known as rigs in some contexts. Extensions like semifields address specific applications in cryptography and coding theory.^[2]

Definition and Fundamentals

Axioms

A semiring is defined as a set S equipped with two binary operations, addition + and multiplication \cdot, such that (S, +) forms a commutative monoid with identity element $0, (S, \cdot) forms a monoid with identity element $1, multiplication distributes over addition on both the left and the right, and the additive identity $0 is absorbing for multiplication, meaning $0 \cdot x = x \cdot 0 = 0 for all x \in S.^[3] These conditions are captured by the following eight axioms, which hold for all x, y, z \in S:

Associativity of addition: (x + y) + z = x + (y + z)
Commutativity of addition: x + y = y + x
Additive identity: x + 0 = 0 + x = x
Associativity of multiplication: (x \cdot y) \cdot z = x \cdot (y \cdot z)
Multiplicative identity: x \cdot 1 = 1 \cdot x = x
Left distributivity: x \cdot (y + z) = (x \cdot y) + (x \cdot z)
Right distributivity: (x + y) \cdot z = (x \cdot z) + (y \cdot z)
Absorption by zero: $0 \cdot x = x \cdot 0 = 0

^[3] The elements $0 and $1 serve as the respective identities for the additive and multiplicative monoids, ensuring a structured algebraic framework; in non-trivial semirings, these identities are distinct, i.e., $0 \neq 1.^[3] Rings arise as a special case of semirings when every element admits an additive inverse.^[1]

Notation and Conventions

In semiring theory, the addition operation is typically denoted by +, which forms a commutative monoid on the underlying set with identity element denoted by [0](/page/0).^[4] The multiplication operation is denoted by \cdot or, when unambiguous, by juxtaposition (e.g., xy instead of x \cdot y), forming a monoid with identity element denoted by $1.^[4] Expressions in semirings are written using these operations in a manner analogous to ring expressions, with multiplication often taking precedence over addition unless parenthesized, and the multiplicative identity $1 acting as a unit for multiplication while the additive identity [0](/page/0) annihilates all elements under multiplication: $0 \cdot a = a \cdot [0](/page/0) = [0](/page/0) for all a in the semiring.^[4] In applied contexts, such as formal language theory or optimization, non-standard operations may be used to emphasize the structure; for instance, generic symbols \oplus for addition and \otimes for multiplication are common, with identities [0](/page/0) and $1 preserved.^[5] In the tropical semiring over the extended reals, the notation \oplus often denotes the minimum (or maximum) operation as "addition," and \otimes denotes ordinary addition as "multiplication," highlighting the deviation from classical arithmetic while maintaining semiring axioms.^[6] Semirings feature concepts like annihilators, which are elements x such that x \cdot a = [0](/page/0) for all a (with [0](/page/0) itself being the trivial left and right annihilator), and zero divisors, which are non-zero elements a and b such that a \cdot b = [0](/page/0).^[4] In contexts involving partial orders, such as naturally ordered or idempotent semirings, the addition + may represent the supremum (join) operation, and the partial order is often denoted by \leq, defined via x \leq y if and only if x + y = y, without altering the core notational conventions for the operations.^[7]

Terminology and Variants

Standard Terminology

In semiring theory, a semiring is termed additively idempotent if its addition operation satisfies x + x = x for all elements x in the semiring, implying that the additive structure forms a join semilattice under the induced order x \leq y if and only if x + y = y. Similarly, a semiring is multiplicatively idempotent if multiplication satisfies x \cdot x = x for all x, making the multiplicative structure a meet semilattice with x \leq y if and only if x \cdot y = x. These properties are independent, allowing semirings to exhibit one, both, or neither, with both cases yielding structures known as idempotent semirings in some contexts. A semiring is zero-sum-free if the equation a + b = 0 holds only when a = [0](/page/0) and b = [0](/page/0), for all elements a, b in the semiring, preventing nontrivial additive combinations from yielding the additive identity. This condition positions zero-sum-free semirings at the opposite end of the spectrum from rings, as it excludes additive inverses entirely beyond the zero element. Semirings without zero divisors—sometimes referred to as positive semirings in certain algebraic contexts—are those where a \cdot b = [0](/page/0) implies a = [0](/page/0) or b = [0](/page/0) for all elements a, b, ensuring multiplication behaves integrally without annihilators.^[8] This absence of zero divisors facilitates unique factorization properties in specific commutative cases, analogous to integral domains in ring theory.^[8] A bounded semiring is one equipped with a partial order compatible with its operations, where addition admits finite suprema and infima, often manifesting as a lattice structure under the order a \leq b if and only if a + b = b. In such semirings, the order ensures boundedness, with every pair of elements having a least upper bound (supremum) and greatest lower bound (infimum) under addition. A selective semiring is defined by the property that a + b \in \{a, b\} for all elements a, b, meaning addition selects one operand, typically the maximum under a compatible total order, rendering the semiring linearly ordered and idempotent additively. Historically, the term "rig" emerged as an alternative to "semiring," coined by John Conway as a portmanteau of "ring" without the "i" for additive inverses, emphasizing the structure's positivity and lack of negatives.^[9] This nomenclature highlights the playful evolution of terminology in abstract algebra during the late 20th century.^[9] In ring theory contexts, "semiring" distinguishes structures lacking additive inverses from "rngs," which are rings without a multiplicative identity but with additive inverses, underscoring the former's emphasis on non-negative-like operations versus the latter's focus on non-unital rings.

Common Variants

A hemiring, also known as a pre-semiring in some contexts, is a variant of a semiring that relaxes the requirement for a multiplicative identity element, while retaining commutative addition with a zero element and the distributivity axiom.^[10] In such structures, the multiplicative operation forms a semigroup rather than a monoid, allowing for broader algebraic applications where unity is not essential. Variants lacking an additive identity omit the zero element for addition, resulting in a commutative semigroup under addition paired with a monoid under multiplication and distributivity.^[11] These structures emphasize the semigroup nature of addition without a neutral element, differing from standard semirings. A related notion is the semiring without a multiplicative identity (also called nonunital semiring), where multiplication is associative but lacks a unit, focusing solely on the semigroup property for multiplication.^[11]^[12] An idempotent semiring requires both addition and multiplication to be idempotent operations, meaning a + a = a and a \cdot a = a for all elements a, in addition to satisfying the standard semiring axioms with identities.^[13] This variant, often studied in optimization and tropical geometry, strengthens the idempotence condition across both operations.^[14] A skew semiring, or non-commutative semiring, permits multiplication to be non-commutative while maintaining commutative addition, a monoid structure for multiplication, and distributivity; this contrasts with commutative semirings by allowing asymmetric products.^[15] Semirings inherently lack additive inverses, distinguishing them fundamentally from rings, where every element has an additive inverse, thus emphasizing positive or non-negative algebraic behaviors without subtraction.^[15] Semirings exist in both finite and infinite forms, with finite variants often arising in combinatorial contexts and infinite ones in analysis or formal languages, though the core axioms remain unchanged across these scopes.^[16]

Basic Examples

Non-negative Numbers

One prominent example of a semiring is the set of non-negative integers \mathbb{N}_0 = \{0, 1, 2, \dots \} equipped with the standard operations of addition + and multiplication \cdot, where $0 serves as the additive identity and $1 as the multiplicative identity. This structure satisfies the semiring axioms: addition is associative and commutative with identity $0, multiplication is associative with identity $1, multiplication distributes over addition, and $0 annihilates under multiplication (i.e., $0 \cdot n = n \cdot 0 = 0 for all n \in \mathbb{N}_0).^[17] Another example is the set of non-negative real numbers \mathbb{R}_{\geq 0} = \mathbb{R}_+ \cup \{0\} under the usual addition and multiplication, which also forms a commutative semiring with the same identities $0 and $1.^[18] This semiring satisfies the standard axioms analogously to the integer case, as the operations inherit their properties from the real numbers while remaining closed on non-negative elements. Moreover, \mathbb{R}_{\geq 0} is a semifield because every non-zero element has a multiplicative inverse within the set.^[18] A distinct numeric example is the tropical semiring on the extended reals \mathbb{R} \cup \{\infty\}, where the addition operation \oplus is defined as the minimum and the multiplication \otimes as standard addition. The explicit operations are given by:

x \oplus y = \min(x, y), \quad x \otimes y = x + y

for x, y \in \mathbb{R} \cup \{\infty\}, with \infty acting as the additive identity (since \min(x, \infty) = x) and $0 as the multiplicative identity (since x + 0 = x). This structure, often called the min-plus semiring, satisfies the semiring axioms, including associativity of both operations, distributivity (\min(x, y + z) = \min(x + y, x + z)), and the annihilation property (\infty + x = \infty). A max-plus variant exists by replacing minimum with maximum, yielding isomorphic structures.

Boolean Semiring

The Boolean semiring, denoted \mathbb{B}, is the two-element set \{[0](/page/0), [1](/page/1)\} equipped with addition + defined as logical disjunction (OR) and multiplication \cdot defined as logical conjunction (AND). The addition operation satisfies [0](/page/0) + [0](/page/0) = [0](/page/0), [0](/page/0) + [1](/page/1) = [1](/page/1) + [0](/page/0) = [1](/page/1), and [1](/page/1) + [1](/page/1) = [1](/page/1), while the multiplication operation satisfies [0](/page/0) \cdot [0](/page/0) = [0](/page/0) \cdot [1](/page/1) = [1](/page/1) \cdot [0](/page/0) = [0](/page/0) and [1](/page/1) \cdot [1](/page/1) = [1](/page/1).^[19] These operations render \mathbb{B} a semiring, with 0 serving as the additive identity and 1 as the multiplicative identity, and multiplication distributing over addition.^[19] The Boolean semiring is both additively and multiplicatively idempotent, meaning x + x = x and x \cdot x = x for all x \in \mathbb{B}. This idempotence arises directly from the properties of OR and AND: disjunction of identical elements yields the element itself, as does conjunction.^[19] In the category of additively idempotent semirings, \mathbb{B} serves as the initial object, admitting a unique homomorphism into any other such semiring.^[20] Equivalently, under the total order $0 < 1, the operations of \mathbb{B} can be expressed using lattice operations: x + y = \max(x, y) and x \cdot y = \min(x, y). This formulation highlights its structure as a bounded lattice, where addition corresponds to the join and multiplication to the meet.^[21] The Boolean semiring is isomorphic to the power set of a singleton set, say \mathcal{P}(\{*\}) = \{\emptyset, \{*\}\}, with addition as set union and multiplication as set intersection; here, \emptyset maps to 0 and \{*\} to 1. This representation underscores its connection to Boolean algebras, where union and intersection preserve the semiring axioms.^[22]

Constructions of Semirings

From Existing Structures

In partially ordered rings, the non-negative cone offers a straightforward construction of a semiring. Let R be a ring equipped with a partial order ≤ compatible with addition and multiplication, such that for all a, b, c ∈ R, if a ≤ b then a + c ≤ b + c, and if 0 ≤ a and 0 ≤ b then 0 ≤ a · b. The subset S = {x ∈ R | 0 ≤ x} contains the additive identity 0 and, assuming the order places 1 above 0, the multiplicative identity 1. Moreover, S is closed under the addition and multiplication of R, inheriting these operations to form a semiring.^[23] In the special case of totally ordered rings, this non-negative cone yields a semiring, whereas the non-positive cone fails to do so because the product of two negative elements is positive and thus lies outside the cone.^[24] Subsemirings provide another method to extract semirings from rings by restricting to suitable subsets. A subset S ⊆ R of a ring R (viewed as a semiring) is a subsemiring if it contains 0 and 1 and is closed under the addition and multiplication operations of R. The induced operations on S satisfy the semiring axioms, though S need not possess additive inverses for all its elements. Rings themselves are semirings in which every element has an additive inverse, but subsemirings generally lack this property. A prototypical example is the set of non-negative integers ℕ₀ = {0, 1, 2, …} under ordinary addition and multiplication, which forms a subsemiring of the ring ℤ of integers.^[25]^[26] Quotient semirings can also be derived from rings via ideals, yielding structures where the full additive inverse property may not be emphasized. For a ring R and a two-sided ideal I ⊆ R, the quotient R/I consists of the cosets {x + I | x ∈ R}, with operations defined by (x + I) + (y + I) = (x + y) + I and (x + I) · (y + I) = (x · y) + I. This quotient inherits the zero coset 0 + I and the identity coset 1 + I (provided I ≠ R), forming a ring and thus a semiring under these operations. While the quotient retains additive inverses as a ring, considering it as a semiring effectively disregards this feature, aligning with broader semiring applications where inverses are absent.^[27]

Matrix and Function Semirings

Given a semiring R, the matrix semiring M_n(R) consists of all n \times n matrices with entries from R. Addition in M_n(R) is defined entrywise using the addition operation of R, making it an abelian monoid with the zero matrix as the identity element. Multiplication is the standard matrix multiplication adapted to R, where for matrices A, B \in M_n(R), the (i,j)-entry of the product AB is computed as

(AB)_{ij} = \sum_{k=1}^n A_{ik} \cdot B_{kj},

using the multiplication and addition from R.^[28]^[29] This construction preserves the semiring axioms: addition is associative and commutative, multiplication is associative, and multiplication distributes over addition because the entrywise nature of addition aligns with the bilinear form of matrix multiplication over R. If R has a multiplicative identity $1 \neq 0, then M_n(R) also has a multiplicative identity given by the identity matrix with $1 on the diagonal and $0 elsewhere. The zero matrix serves as the additive identity, and the structure satisfies the required absorption properties if present in R.^[28]^[29] Function semirings provide another key construction from a base semiring. For a set S and semiring R, the set R^S of all functions f: S \to R forms a semiring under pointwise addition and multiplication: (f + g)(s) = f(s) +_R g(s) and (f \cdot g)(s) = f(s) \cdot_R g(s) for all s \in S, where +_R and \cdot_R are the operations in R. The constant function mapping to $0_R is the additive identity, and if R has a multiplicative identity $1_R, the constant function mapping to $1_R serves as the multiplicative identity. This pointwise structure inherits the semiring properties directly from R, with distributivity holding componentwise.^[30] When applicable, composition can define multiplication in function semirings. For an abelian monoid (M, +_M, 0_M), the endomorphism semiring \mathrm{End}(M) consists of functions f: M \to M preserving the monoid operation (i.e., f(a +_M b) = f(a) +_M f(b)), with addition pointwise: (f + g)(m) = f(m) +_M g(m), and multiplication as composition: (f \cdot g)(m) = f(g(m)). The zero map (constant to $0_M) is the additive identity, and the identity map is the multiplicative identity. Distributivity follows from the linearity of endomorphisms over the monoid addition. This construction generalizes to functions between sets S and T where composition is possible (e.g., S = T and T admits a suitable structure), yielding semirings that model transformations in algebraic settings.^[30]^[31]

General Properties

Algebraic Identities

In a semiring (S, +, \cdot, 0, 1), the multiplication distributes over addition on both sides, satisfying the identities x \cdot (y + z) = x \cdot y + x \cdot z and (x + y) \cdot z = x \cdot z + y \cdot z for all x, y, z \in S. Additionally, the additive identity acts as a multiplicative absorber (or annihilator), with $0 \cdot x = x \cdot 0 = 0 for all x \in S, and the multiplicative identity satisfies $1 \cdot x = x \cdot 1 = x for all x \in S. These, together with the monoid axioms for (S, +) and (S, \cdot), form the core structure. From the additive monoid axioms, it follows directly that x + 0 = 0 + x = x for all x \in S, establishing the role of $0$ as the additive neutral element (annihilator in the sense of absorption under addition). However, unlike rings, semirings lack additive inverses, so no subtraction or negative elements exist, preventing identities involving differences. A key theorem concerns additive cancellativity: if (S, +) is cancellative—meaning a + c = b + c implies a = b for all a, b, c \in S—then the absorption laws $0 \cdot x = 0 and x \cdot 0 = 0 follow from distributivity alone.^[15] To see this, note that x \cdot 0 = x \cdot (0 + 0) = x \cdot 0 + x \cdot 0; left cancellation under addition then yields x \cdot 0 = 0. The argument for $0 \cdot x = 0 is symmetric.^[15] Such cancellative semirings imply stronger algebraic structures, often resembling semifields or integral domains in restricted cases, but additive cancellativity is rare among common semirings (e.g., it fails in idempotent examples like the tropical semiring).^[15]

Canonical Representations

In semiring theory, an analogue of Rees's theorem characterizes completely simple semirings as those isomorphic to a Rees matrix semiring M(I, R, \Lambda; P), where I and \Lambda are index sets forming left and right zero semigroups under addition, R is a skew-ring, and P: \Lambda \times I \to R is a sandwich matrix satisfying regularity conditions such as the existence of inverses in rows and columns to ensure simplicity.^[32] This decomposition highlights the ideal structure, where the semiring decomposes into principal ideals generated by the matrix entries, analogous to the Rees matrix construction over groups in semigroup theory but adapted to the absence of additive inverses.^[32] Green's relations, originally defined for semigroups, are adapted to semirings by applying them separately to the additive monoid and the multiplicative semigroup. For the multiplicative structure, the relations \mathcal{L}, \mathcal{R}, \mathcal{H}, \mathcal{D}, and \mathcal{J} classify elements based on generated principal left, right, and two-sided ideals, while additive variants \mathcal{L}^+, \mathcal{R}^+, etc., do the same for the addition operation. In quasi completely regular semirings, these relations facilitate decomposition into \mathcal{H}^+-classes, each forming a quasi skew-ring, providing a structural breakdown without assuming commutativity or inverses. Representations as spans of idempotents arise in this context, where regular elements in the multiplicative semigroup can be expressed as linear combinations (under addition) of primitive idempotents spanning principal ideals, particularly in completely 0-simple semirings where such idempotents characterize the simplicity.^[33] For finite semirings, a canonical form emerges from semisimplicity: every finite semisimple semiring decomposes as a subdirect product of primitive semirings, and since finiteness implies the components are congruence-simple, this yields a direct product decomposition.^[34] Primitive semirings, defined as those admitting a faithful simple (or minimal) semimodule, take the form of transitive endomorphism semirings over a division semiring D (where every nonzero element is invertible under multiplication), often realized as full matrix semirings M_n(D) for finite dimension n, mirroring the Artin-Wedderburn theorem for rings but over semifields or division semirings.^[34] Commutative primitive semirings are limited to the 2-element Boolean semiring or fields, ensuring the decomposition captures the full algebraic structure.^[34]

Special Classes of Semirings

Commutative and Idempotent Semirings

A commutative semiring is a semiring (S, +, \cdot, 0, 1) in which both the addition and multiplication operations are commutative, meaning a + b = b + a and a \cdot b = b \cdot a for all a, b \in S.^[4] This commutativity ensures that the additive monoid (S, +, 0) is abelian and the multiplicative monoid (S, \cdot, 1) is abelian.^[4] Commutative semirings generalize commutative rings by omitting the requirement for additive inverses while preserving the commutativity of both binary operations; the absence of negatives distinguishes them structurally from rings, though many ring-theoretic concepts like ideals extend to this setting with modifications.^[35] An idempotent semiring, also known as an additively idempotent semiring or dioid, satisfies a + a = a for all a \in S. In such structures, the additive operation turns (S, +, 0) into a join-semilattice with least element $0, where the canonical partial order is defined by a \leq bif and only ifa + b = b$. When the semiring is also commutative, this semilattice structure aligns with the abelian additive monoid, enhancing the algebraic interplay between the operations. A canonical example of a commutative idempotent semiring is the max-plus algebra over the extended real line \mathbb{R} \cup \{-\infty\}, where addition is the maximum operation \oplus = \max (idempotent and commutative) and multiplication is ordinary addition \otimes = + (commutative), with identities -\infty for \oplus and $0for\otimes$.^[36] This semiring's lattice-like additive structure underpins applications in optimization and scheduling, where paths or resources are aggregated via maxima.^[36] Commutative idempotent semirings exhibit lattice aspects through their additive semilattice, with distributivity ensuring that multiplication respects the join structure: a \cdot (b + c) = a \cdot b + a \cdot c and (b + c) \cdot a = b \cdot a + c \cdot a, allowing elements to act as lattice homomorphisms in certain contexts.

Ordered Semirings

An ordered semiring is a semiring (S, +, \cdot, 0, 1) equipped with a partial order \leq on S that is compatible with the semiring operations in the following sense: for all x, y, z \in S, if x \leq y, then x + z \leq y + z, x \cdot z \leq y \cdot z, and z \cdot x \leq z \cdot y.^[4] Additionally, $0is the minimal element ofSwith respect to\leq, so 0 \leq xfor allx \in S

, and &#36;1

is positive, meaning $0 \leq 1.^[37] This compatibility ensures that the order respects both addition and multiplication, allowing ordered semirings to model structures where monotonicity is essential, such as in optimization problems or formal language theory.^[38] The positive cone of an ordered semiring (S, +, \cdot, 0, 1, \leq) is the subset P = \{ x \in S \mid 0 \leq x \}, which includes all elements greater than or equal to the additive identity.^[4] In many cases, particularly when $0is minimal, the entire semiringScoincides with{0} \cup P, reflecting the absence of negative elements inherent to semirings. The positive cone P$ itself often forms a subsemiring under the induced operations, providing a foundation for studying order-preserving homomorphisms and ideals within ordered semirings.^[37] In the context of arithmetic and logic, a discretely ordered semiring is an ordered semiring equipped with a total discrete order \leq, meaning the order is linear and every element x \in S has an immediate successor y, i.e., x < y and there is no z with x < z < y. This property ensures that the order has no dense intervals, distinguishing discretely ordered semirings from those with continuous orders and enabling applications in discrete mathematics, such as automata theory over countable structures.^[39] A prototypical example is the semiring of non-negative integers (\mathbb{N}_0, +, \cdot, 0, 1, \leq), where the order is total and discrete, with each n having immediate successor n+1. An example of an ordered semiring that is not discretely ordered is the set of non-negative real numbers \mathbb{R}_{\geq 0} = [0, \infty) equipped with the usual addition +, multiplication \cdot, zero $0

, one &#36;1

, and the standard order \leq.^[40] Here, the order is total rather than merely partial, and the positive cone is \mathbb{R}_{>0} \cup \{0\}, illustrating a continuously ordered structure without discrete successors.^[4]

Complete and Continuous Semirings

Complete Semirings

A complete semiring is an algebraic structure (S, +, \cdot, 0, 1) where the additive monoid (S, +, 0) forms a complete join-semilattice, meaning every subset of S has a least upper bound (supremum) with respect to the natural order induced by addition, and addition + coincides with this join operation; additionally, multiplication \cdot is continuous, preserving arbitrary suprema in each argument separately: for any s \in S and subset A \subseteq S, s \cdot (\sup A) = \sup \{ s \cdot a \mid a \in A \} and (\sup A) \cdot s = \sup \{ a \cdot s \mid a \in A \}.^[41] This definition ensures that infinite operations are well-defined and compatible with the semiring axioms, extending finite distributivity to arbitrary families.^[42] In complete semirings, arbitrary sums over an index set I are defined as the supremum of all finite partial sums: \sum_{i \in I} x_i = \sup \left\{ \sum_{j \in J} x_j \;\middle|\; J \subseteq I, \, |J| < \infty \right\}.^[41] This construction leverages the completeness of the join-semilattice to handle infinite aggregations naturally, with the empty sum equaling the additive identity 0 and singletons reducing to the element itself.^[42] Key properties of complete semirings include the inheritance of completeness by subsemirings: any subsemiring of a complete semiring, closed under addition and multiplication while containing 0 and 1, is itself complete, as it embeds the join-semilattice structure and continuous multiplication from the ambient semiring.^[41] Furthermore, complete semirings are intimately related to quantales, with every unital quantale— a complete lattice equipped with an associative multiplication distributing over arbitrary joins—serving as an example of a complete semiring where addition is the lattice join.^[41] The continuity of multiplication manifests in the infinite distributivity law: for any x \in S and indexed family (y_i)_{i \in I},

x \cdot \left( \sum_{i \in I} y_i \right) = \sum_{i \in I} (x \cdot y_i),

with a symmetric equation holding for right distributivity.^[42] This equation underpins the robustness of complete semirings in applications requiring summation over unbounded sets, such as in formal power series and automata theory.^[42] Complete semirings extend the framework of ordered semirings by demanding the existence of suprema for arbitrary rather than merely finite subsets.^[41]

Continuous Semirings

A continuous semiring is an ordered semiring S equipped with a complete partial order (cpo) whose least element is the additive identity $0, such that the addition and multiplication operations are continuous, meaning they preserve the suprema of directed sets (or \omega-chains in the \omega-continuous case).^[43] This structure extends the notion of completeness in semirings by ensuring that operations respect limits in the order topology, allowing for the handling of infinite processes algebraically. Unlike rings, continuous semirings lack additive inverses, which limits their invertibility but enables applications in non-negative or monotonic settings.^[44] A prominent example is the semiring [0, \infty] of extended non-negative real numbers, with usual addition and multiplication extended to include \infty, and the standard order where \infty is the greatest element.^[43] Here, addition and multiplication are continuous with respect to the order topology, as suprema correspond to limits of increasing sequences. Another key example arises in formal power series: given a continuous semiring S and a finite alphabet \Sigma, the set S\langle\langle \Sigma^* \rangle\rangle of formal power series (functions from \Sigma^* to S with finite support or well-defined sums) forms a continuous semiring under pointwise addition and the Cauchy product for multiplication.^[43] In this construction, series convergence is guaranteed by the continuity of operations, enabling the summation of infinite series as suprema of finite partial sums.^[45] Properties of continuous semirings emphasize the convergence of series and iterative processes. Infinite sums \sum_{i \in I} a_i are defined as the supremum of all finite subsums, and continuity ensures that such series converge in the order.^[43] This relates to analytic structures like C*-algebras, where continuous operations on normed spaces handle limits, but continuous semirings operate without inverses or norms, focusing instead on order-preserving monotonicity. For idempotent operations—where addition satisfies a + a = a, inducing a semilattice structure—multiplication remains continuous, preserving fixed points under iteration.^[46] Fixed-point theorems underpin much of the theory in continuous semirings, particularly for solving equations of the form x = f(x) where f is a continuous, order-preserving function. By the Knaster-Tarski fixed-point theorem adapted to cpos, every such f has a least fixed point, given by the supremum of the iterates starting from $0: \mu x. f(x) = \sup \{ f^n(0) \mid n \geq 0 \}.^[43] In the idempotent case, where the semiring is additively idempotent and \omega-continuous, systems of polynomial fixed-point equations admit unique least solutions computable via algebraic methods, such as value iteration or derivation trees, without cycles in the dependency graph.^[47] These theorems extend completeness by ensuring convergence for countable iterations, linking back to suprema in complete semirings.^[44]

Star Semirings

A star semiring is a semiring (S, +, \cdot, 0, 1) equipped with a unary star operation * : S \to S satisfying the fixed-point equation x^* = 1 + x \cdot x^* for all x \in S.^[48] This equation ensures that the star operation captures infinite iteration in a recursive manner, analogous to the Kleene star in formal language theory. The operation also satisfies the symmetric unfolding axiom x^* = 1 + x^* \cdot x, which follows from the semiring structure and the primary equation.^[49] Key properties of star semirings include the existence of a unique solution to certain linear recursive equations. Specifically, for any x, y \in S, the equation z = y + x \cdot z has a unique least solution z = x^* \cdot y, and similarly z = y + z \cdot x has solution z = y \cdot x^*.^[48] More generally, the iteration lemma states that x^* \cdot y = y + x \cdot (x^* \cdot y), highlighting the star's role in solving fixed-point equations without requiring additive inverses.^[5] These properties enable the star operation to model repeated applications of elements, foundational for iterative processes in algebraic structures. In additively idempotent star semirings, where x + x = x for all x \in S, the star operation aligns closely with the semantics of regular expressions over formal languages. Here, addition represents union (idempotent), multiplication concatenation, and the star unbounded repetition, satisfying additional identities like (x^*)^* = x^* and $1^* = 1.^[5] A fundamental distributivity equation is (x + y)^* = x^* \cdot (y \cdot x^*)^*, which facilitates the manipulation of expressions involving sums and iterations.^[49] Such semirings often arise in complete settings, where infinite sums are defined to ensure convergence of the star as a supremum.^[48]

Conway Semirings

A Conway semiring is a semiring equipped with a unary star operation * that satisfies three key axioms, providing an axiomatic framework for iteration without assuming completeness or an underlying order structure.^[43] The first axiom is the fixed-point identity: x^* = 1 + x x^* for all x in the semiring, ensuring that the star operation captures infinite iteration as a solution to an equation.^[43] The second axiom, the sum-star identity, states that (x + y)^* = x^* (y x^*)^* for all x, y, allowing the star of a sum to be expressed in terms of starred components under suitable conditions.^[50] The third axiom, the product-star identity, is (x y)^* = 1 + x (y x)^* y for all x, y, which handles the star of a product by incorporating finite and infinite compositions.^[50] These axioms, originally formulated by John Conway in the context of regular algebra, ensure that the star operation behaves consistently for expressions modeling sequential processes.^[51] Conway semirings are closely related to bimonoids through their role in algebraic models of concurrency and iteration, where the additive and multiplicative structures form commutative monoids compatible with the star operation.^[52] More precisely, they underpin iteration theories, which are categorical structures generalizing matrix semirings over Conway semirings; the matrix construction over a Conway semiring yields a Conway theory, and adding group identities produces a full iteration theory for equational reasoning about fixed points.^[50] In ordered Conway semirings, where a partial order is compatible with addition and multiplication (making the semiring positively ordered), the star operation admits a fixed-point characterization: x^* is the least element satisfying y = 1 + x y, enabling inductive proofs via the Knaster-Tarski theorem adapted to the semiring context.^[50] This least-fixed-point property arises from the monotonicity of the operations, allowing x^* y^* \leq (x + y)^* and other inequalities to hold naturally.^[43] Unlike Kleene semirings or algebras, which rely on completeness or order to establish an iteration theorem equating regular expressions to automaton behaviors, Conway semirings lack such a theorem in the absence of an order; the axioms alone do not guarantee the equivalence of syntactic and semantic models without additional structure.^[50]

Applications

Formal Languages and Automata

Semirings provide a unifying algebraic structure for extending classical automata theory to weighted models, where transitions in finite automata are labeled not only by symbols from an alphabet but also by elements from a semiring to represent weights or costs. In this framework, a weighted automaton over a semiring (S, \oplus, \otimes, 0, 1) accepts a string by computing the \oplus-sum of all path weights from initial to final states, yielding a value in S that indicates acceptance or a quantitative measure.^[53] For instance, the Boolean semiring (\{0,1\}, \lor, \land, 0, 1) recovers the standard nondeterministic finite automaton (NFA), where weights are absent and acceptance is binary.^[53] Similarly, the min-plus semiring (\mathbb{R} \cup \{\infty\}, \min, +, \infty, 0) assigns additive weights to transitions, enabling automata to compute shortest path distances in graphs represented as languages. The recognition of regular languages extends naturally to this setting through matrix semirings. Given a finite alphabet \Sigma, the semiring of n \times n matrices over S with entries in S \cup \Sigma (where symbols act as basis elements) allows the powers of an automaton's adjacency matrix to encode the weighted language accepted by the automaton.^[53] Specifically, the (i,j)-entry of the matrix A^k gives the \oplus-sum of weights of paths of length k from state i to j, and summing over all lengths via the Kleene star operation yields the full language.^[53] This matrix approach underpins algorithms for language recognition and minimization in the weighted case.^[53] A generalized Kleene theorem establishes the equivalence between automata-recognizable formal power series and rational expressions over continuous semirings. In a continuous semiring, infinite \oplus-sums are well-defined and compatible with the order, allowing the star operation a^* = \bigoplus_{n=0}^\infty a^n to be the least fixed point of the equation x = 1 \oplus a \otimes x.^[54] The theorem states that the power series recognized by finite weighted automata are precisely those generated by rational expressions closed under star, mirroring the classical result for regular languages over the Boolean semiring.^[54] This correspondence holds for any continuous semiring, enabling the theory to apply uniformly to diverse weight structures like probabilities or lengths.^[54] Algebraically, each formal language admits a syntactic semiring, defined as the quotient of the free semiring on the monoid of words by the syntactic congruence that identifies words based on their contextual equivalence with respect to the language.^[55] This semiring is the smallest complete semiring recognizing the language, generalizing the syntactic monoid from classical theory to capture both union and concatenation operations.^[55] Finite syntactic semirings characterize rational languages over arbitrary semirings, providing an invariant for language equivalence and minimization.^[55] Semirings have been applied to parsing algorithms and transducer theory since the 1950s, with foundational contributions by Marcel-Paul Schützenberger on rational transductions and automata realizations.^[56] Schützenberger's work established that rational transductions—relations between input and output strings computable by finite transducers—correspond to matrix representations over semirings of rational subsets, influencing modern parsing frameworks that unify probabilistic, deductive, and logical inference via semiring polymorphisms.^[57] This algebraic perspective, extended in subsequent decades, supports efficient algorithms for weighted context-free parsing and transducer composition in natural language processing.^[57]

Optimization and Tropical Geometry

Semirings play a pivotal role in optimization problems through the framework of tropical algebra, where the tropical semiring, often denoted as (\mathbb{R} \cup \{+\infty\}, \min, +), replaces conventional addition with minimization and multiplication with addition. This structure, known as the min-plus semiring, enables the reformulation of shortest path problems in weighted graphs as matrix operations over the semiring. Specifically, the all-pairs shortest paths (APSP) problem can be solved using variants of the Floyd-Warshall algorithm, which computes the semiring closure of the adjacency matrix, yielding the minimum path weights between all pairs of vertices.^[3] In this setting, matrix multiplication corresponds to combining paths via the min-plus operations, allowing efficient dynamic programming approaches that generalize classical graph algorithms to idempotent structures.^[3] Tropical geometry extends this algebraic foundation to the study of varieties defined over the min-plus semiring, where classical polynomial equations are tropicalized by replacing sums with minima. A tropical variety is the closure of the image of a classical algebraic variety under the valuation map, resulting in polyhedral complexes that capture the combinatorial skeleton of the original geometry. These varieties, often realized as balanced polyhedral fans in \mathbb{R}^n, facilitate the analysis of degenerations and asymptotics in algebraic geometry. Idempotent analysis, a related framework, interprets optimization and differential equations over idempotent semirings, providing tools for variational problems where minima replace integrals, as developed in the context of Maslov dequantization. Since the 2000s, tropical semirings have found significant applications in operations research, particularly in scheduling and network flow optimization, where min-plus algebra models resource allocation and critical path analysis in project management. In phylogenetics, tropical geometry offers a metric space for tree reconstruction, enabling the study of evolutionary distances via tropical distances on the space of phylogenetic trees, which aligns with quartet-based methods and principal component analysis adapted to the max-plus semiring. For instance, tropical principal component analysis has been applied to dimensionality reduction of distance matrices from genetic data, revealing hierarchical structures in tree spaces. A key concept in tropical linear algebra is the tropical eigenvalue of a matrix A \in (\mathbb{R} \cup \{+\infty\})^{n \times n}, defined as the minimum cycle mean in the associated weighted digraph:

\lambda(A) = \min_{\sigma} \frac{\sum_{e \in \sigma} w(e)}{|\sigma|},

where the minimum is over all simple cycles \sigma, w(e) is the weight of edge e, and |\sigma| is the cycle length. This eigenvalue characterizes the growth rate in min-plus powers of A and is computable via parametric shortest path algorithms or Howard's policy iteration.^[58]

Generalizations

Hemirings and Near-Rings

A hemiring is a generalization of a semiring that omits the requirement for a multiplicative identity element.^[59] In a hemiring S = (S, +, \cdot, 0), the set S is equipped with two binary operations such that (S, +) forms a commutative monoid with identity $0, (S, \cdot) forms a semigroup, multiplication distributes over addition on both sides, and $0 acts as a zero element by annihilating all other elements: $0 \cdot s = s \cdot 0 = 0 for all s \in S.^[59] This structure weakens the standard semiring axioms, which include both an additive identity and a multiplicative identity $1 satisfying $1 \cdot s = s \cdot 1 = s for all s \in S.^[59] Hemirings arise naturally in contexts where a full multiplicative unit is unnecessary, such as in the study of incidence algebras over partially ordered sets, where the convolution product may not require an identity beyond the delta function at the minimal element.^[60] A near-ring, in contrast, relaxes the distributivity and additively closed properties of rings to explore non-distributive relatives of semirings.^[61] Formally, a near-ring N = (N, +, \cdot) consists of a group (N, +) under addition, a semigroup (N, \cdot) under multiplication, and left distributivity: (a + b) \cdot c = a \cdot c + b \cdot c for all a, b, c \in N, without requiring right distributivity or additive commutativity beyond the group structure.^[61] The concept of near-rings was developed by Hans Zassenhaus in the 1930s, initially in the context of near-fields as structures intermediate between fields and rings.^[62] Semirings relate to near-rings through embeddings, particularly into those with zero-symmetric addition, where the zero element satisfies $0 \cdot n = n \cdot 0 = 0 for all n \in N; this allows semirings, with their commutative monoid addition and identities, to be realized within the broader framework of near-rings by extending the additive structure appropriately.^[63]

Bimonoids and Beyond

A bimonoid is an algebraic structure consisting of a set equipped with two monoid operations—typically addition and multiplication—that satisfy compatibility conditions such as the existence of distributive scalars from the natural numbers, but without requiring full distributivity of multiplication over addition. Semirings arise as the special case of bimonoids where multiplication fully distributes over addition on both sides. This perspective highlights how semirings impose additional constraints on the more general bimonoid framework, enabling applications in weighted automata where the lack of full distributivity allows for broader algebraic behaviors.^[64]^[65] In category theory, semirings and bimonoids can be formalized using PROPs, which are symmetric strict monoidal categories with objects generated by the natural numbers, providing a universal framework for algebraic theories involving multiple operations like addition and multiplication. The PROP associated with semirings encodes these operations and their axioms, allowing models (such as actual semirings) to be interpreted as PROP-homomorphisms into the category of sets. Similarly, linear species—functors from the category of finite sets and bijections to vector spaces or modules—extend to semiring coefficients, facilitating combinatorial interpretations where semiring operations govern summation and scalar multiplication in species compositions.^[66]^[67] Generalizations of semirings to structures like supertropical semirings introduce "ghost" elements to resolve singularities in tropical algebra, enhancing the ability to model layered or hierarchical computations without losing algebraic closure properties. Fuzzy semirings, on the other hand, replace the underlying set with a lattice (often [0,1]) and define operations via fuzzy intersections and unions, providing a framework for incorporating degrees of membership and handling imprecision in uncertainty modeling, such as in decision processes or approximate reasoning. These extensions maintain the core monoid structures while adapting to specific needs in non-classical settings.^[68] Semirings also underpin enriched category theory through V-categories, where V is the one-object monoidal category whose endohom-set is the semiring, with tensor given by multiplication and unit by the multiplicative identity. In a V-category, hom-objects take values in the semiring, and composition is mediated by the semiring's multiplication, generalizing ordinary categories to settings where morphisms carry "weights" or "costs" from the semiring, such as distances in metric spaces or probabilities in probabilistic categories. This enrichment preserves key categorical constructions like limits and adjoints under suitable conditions on the semiring.^[69]

References

[1]
Semirings and their Applications
Semirings abound in the mathematical world around us. Indeed, the first mathe- matical structure we encounter - the set of natural numbers - is a semiring.
[2]
Introduction
We will consider the notion of semiring in the most inclusive sense: as the general algebra (5; +, .) with two binary associative operations: "+" and. ".", such ...
[3]
[PDF] Semiring Frameworks and Algorithms for Shortest-Distance Problems
Semirings. Definition 1 A semiring is a system (K, ⊕, ⊗, 0, 1) such that: 1. (K, ⊕, 0) is a commutative monoid with 0 as the identity element for ⊕,. 2 ...
[4]
[PDF] Orderings on semirings - Department of Mathematics
semiring will be defined to be a set S with two operations + (addition) and. 9 (multiplication); with respect to addition, S is a commutative monoid with.
[5]
[PDF] CDM [2ex] Semirings, Rings, Fields - Carnegie Mellon University
and 1 are the appropriate null and identity matrices over S. ... is a semiring, the fusion semiring over Γ. Page ... addition and multiplication for a ring. Example ...
[6]
[PDF] What Is a Tropical Line? - Berkeley Math Circle
Tropical semiring is the real numbers R with operations of tropical sum x ⊕ y := min(x, y) and tropical product x y := x + y. While R with usual operations is ...<|control11|><|separator|>
[7]
[PDF] Axioms of Kleene Algebra
Example 9 is never commutative for any X with at least 2 elements. Idempotent Semirings. A semiring is an algebraic structure (S, +, ·, 0, 1) such that.
[8]
[PDF] Hebisch, U. and Weinert, H. J.: Semirings without zero divisors
Semirings without Zero Divisors general concepts and statements on semirings in Section 2. 75 ... non-negative integers, define operations by. (6.5). (6.6). (V1, ...
[9]
rig in nLab
Jun 14, 2025 · (Terminology: Rigs and semirings) Rigs are commonly also called semirings, but the term 'semiring' is overloaded in the mathematics literature, ...
[10]
[PDF] arXiv:1603.03201v2 [math.AC] 25 Jan 2018
Jan 25, 2018 · In this paper, by a “pre-semiring”, we understand an algebraic structure, consisting of a nonempty set S with two operations of addition and ...
[11]
semiring in nLab
Apr 11, 2025 · There are 4 different definitions of a semiring used in mathematics: A semigroup object in the category of commutative semigroups.Missing: axioms | Show results with:axioms
[12]
Semiring - Typelevel
Semiring consists of: a commutative monoid for addition (+); a semigroup for multiplication (*). Alternately, a Semiring can be thought of as a ring without ...
[13]
Idempotent semi-ring - Encyclopedia of Mathematics
Nov 16, 2023 · There is a natural partial order on any idempotent semi-ring (as well as on any idempotent semi-group; cf. also Idempotent semi-ring). By ...
[14]
A Note on Idempotent Semirings - AIP Publishing
The set of all idempotent elements is denoted by E(G). In the set E(G) there is a partial natural order: e ≤ f iff e · f = f · e = e for ...
[15]
Exact rings and semirings - ScienceDirect.com
Aug 15, 2013 · A semiring is an algebraic structure satisfying the usual axioms for a (not necessarily commutative) ring, but without the requirement that ...
[16]
[PDF] Different Differences in Semirings - DROPS
We show that, in order to preserve all identities valid under bag semantics, one must ensure that the semiring satisfies all identities that hold in (N, +, ·, 0 ...
[17]
On Some Additive Properties of Multiplicative Subsemigroups ... - arXiv
Dec 22, 2009 · As an application, we study and analyze several classical problems in additive number theory on the semiring of non-negative integers by ...
[18]
Which semifields are exact? - ScienceDirect.com
Dec 15, 2017 · Various examples of semifields arise in different applications, and they include the division rings, the semiring of nonnegative reals [13], the ...
[19]
[PDF] NOTES ON BOOLEAN READ-K CIRCUITS 1. Introduction. Let F be ...
May 1, 2025 · A monotone Boolean circuit is a circuit over the Boolean semiring (⊕, ⊙) with x ⊕ y := x ∨ y and x ⊙ y := x ∧ y; the domain is {0, 1}. We will ...
[20]
https://www.sciencedirect.com/science/article/pii/S0001870815300815
[21]
[PDF] Indecomposability Over the Max-Min Semiring - Williams College
Dec 29, 2022 · As noted previously, the semiring of sets under union and set addition is isomorphic to the semiring of boolean polynomials [5]. Hence ...
[22]
(PDF) Semirings and Formal Power Series - ResearchGate
This chapter presents basic foundations for the theory of weighted automata: semirings and formal power series.<|control11|><|separator|>
[23]
[PDF] ARITHMETIC OF SEMIGROUP SEMIRINGS | Vadim Ponomarenko
Introduction. The study of group rings is very popular and active, e.g. [7]. Similarly, the study of semigroup rings has a rich history, e.g. [8].
[24]
[PDF] An Introduction to Γ-Semirings - m-hikari.com
We recall here that the non-negative cones of the totally ordered rings form semirings but the non-positive cones do not form semirings because ... Chanda, ...
[25]
[PDF] arXiv:1509.03354v3 [math.AC] 30 Mar 2017
Mar 30, 2017 · We define a semiring S to be a valuation semiring, if there exists an M-valuation v on K, where K is a semifield containing S as a subsemiring, ...
[26]
[PDF] Difference Ordered Γ− Semirings
May 30, 2024 · A natural example of a semiring, which is not a ring, is the set of all non-negative integers under usual addition and multiplication. There ...
[27]
https://math.hawaii.edu/~tom/old_classes/412notes6.pdf
[28]
[1907.12518] Matrix semigroups over semirings - arXiv
Jul 29, 2019 · This paper considers semigroups of the form M_n(S), where S is a semiring, and the subsemigroups UT_n(S) and U_n(S) of M_n(S) consisting of ...Missing: construction | Show results with:construction
[29]
[PDF] Maximal Endomorphism Semirings
under pointwise addition and composition of functions. Let M0(A) := {f : A ... function composition, is a semiring contained in Map(M). Here we can have ...
[30]
Endomorphism Semirings – an Overview - AIP Publishing
h = f · g when h(x) = f (g(x)) for all x ∈ M. This semiring is called the endomorphism semirimg of M. Clearly the semiring EM is an additively idempotent.
[31]
[PDF] Completely Regular Semirings
So, chapter 3 contains various results about completely simple semirings including a Rees like representation of them.
[32]
Completely $0$-Simple Semirings - jstor
If R is a completely 0-simple semiring, the structure of (R, *) is given by. Theorem 2.1(iv) and the Rees-Sushkevitsch theorem. On the other hand the only.
[33]
https://www.jstor.org/stable/1995461
[34]
Resultants over commutative idempotent semirings I: Algebraic aspect
1. Introduction. The main contribution of this paper is adapting a certain important algebraic property of resultant (over commutative rings) to commutative ...<|control11|><|separator|>
[35]
[PDF] Max Plus at Work is published by Princeton Univ
Such a semiring is denoted by R = (R, ⊕R, ⊗R,εR,eR). If ⊗R is commutative, then R is called commutative, and if ⊕R is idempotent, then it is called idempotent.
[36]
Partially-ordered semirings - SpringerLink
Download book PDF · Semirings and Affine Equations over Them ... About this chapter. Cite this chapter. Golan, J.S. (2003). Partially-ordered semirings.
[37]
[PDF] k IDEALS OF ORDERED SEMIRINGS M. MURALI KRISHNA RAO
Then (M, max, min) is a semiring. Definition 2.4. A semiring M is called an ordered semiring if it admits a compatible relation ≤ . i.e. ≤ is a partial ...
[38]
Characterizations of ordered -regular semirings by ordered -ideals
If E is both left ordered ideal and right ordered ideal of S, then E is ordered ideal of S. Definition 7. Suppose S is an ordered semiring, if ...
[39]
[PDF] Lecture 5 - Math 225A – Model Theory
The algebraic axioms basically state. (in the formal language 多 (τ)) that (N,0,1,+,·,<) is a discretely ordered semi-ring. They may be stated as follows ...<|separator|>
[40]
[PDF] computability-theoretic and proof-theoretic aspects of partial and ...
1-)comprehension, together with the basic axioms of a discretely ordered semiring, as above, and Σ0. 1-induction, as we define below.) In his address to the ...
[41]
Structure of Ordered Semimodules - AIP Publishing
Definition: If (R,⊕,⊗,≤) is the positive cone of an ordered field, then H is called an ordered semivector space over. R. Some Results On Ordered Semirings and ...
[42]
[PDF] arXiv:1510.01478v1 [math.RT] 6 Oct 2015
Oct 6, 2015 · Complete semirings and homomorphisms form a subcategory in SRing, denoted by CSRing. Here are some examples of complete semirings: • Any bounded ...
[43]
Semirings and Formal Power Series - SpringerLink
This chapter presents basic foundations for the theory of weighted automata: semirings and formal power series.
[44]
[PDF] Inductive -Semirings - BRICS
The Kleene theorem in countably complete semirings. Bayreuther Mathematische Schriften, 31:55-66, 1990. [15] R. Kimmo. Quantales and Their Applications.
[45]
[PDF] Greibach Normal Form in Algebraically Complete Semirings - BRICS
Dec 28, 2002 · We now give some examples of algebraically complete semirings. Example 3.4 A continuous semiring is a semiring S = (S,+, ·, 0, 1) equipped with ...
[46]
[PDF] Modern Automata Theory
Here 2S denotes the power set of a set 𝑆 and ∅ denotes the empty set. ... Boolean semiring, 𝑟 ∈ 𝔹⟨⟨𝑋∗⟩⟩ is a macro power series iff supp(𝑟) ...
[47]
[PDF] Idempotent analysis and continuous semilattices
May 28, 2004 · idempotent semiring is that of a semilattice ... a satisfactory linear algebra, typically referred to as max-plus algebra, that shares many.
[48]
[PDF] On Fixed Point Equations over Commutative Semirings - TUM
Examples of semirings include hN ∪ {0, ∞}, +, ·, 0, 1i, hR+ ∪ {0, ∞}, + ... Let x = f(x) be a system of power series over an ω-continuous semiring.
[49]
*-μ-semirings and *-λ-semirings
**Paper Title:** On ω-Semirings and ω-Continuous Semirings
[50]
[PDF] CS 6861 S24 Lectures 5–6 Axiomatizations of KA Week of February ...
Generalizations of Kleene's and Parikh's Theorems have been given by Kuich [10] in ℓ-complete semirings, which are similar to S-algebras in all respects except ...
[51]
[PDF] Conway and Iteration Semirings - LMPA
Definition. A Conway semiring is star semiring satisfying the sum and product star identities. Examples. • Language semirings ...
[52]
Iteration Semirings | SpringerLink
An iteration semiring is a Conway semiring satisfying Conway's group equations. ... Conway, J.C.: Regular Algebra and Finite Machines. Chapman and Hall, Boca ...
[53]
Weighted finite automata over hemirings | Semantic Scholar
This work investigates the question under which conditions on the strong bimonoid ... bimonoids and in ... Conway semiring. Expand. 12 Citations. Add to ...
[54]
Semirings, Automata, Languages - SpringerLink
The purpose of this book is to develop the theory of automata and formal languages, starting from ideas based on linear algebra.
[55]
Automata and languages generalized to ω-continuous semirings
We generalize the following two language- and automata-theoretic results to ω-continuous semirings. ... Kuich. The Kleene and the Parikh Theorem in complete ...
[56]
Syntactic Semiring of a Language - SpringerLink
A classical construction assigns to any language its (ordered) syntactic monoid. Recently the author defined the so-called syntactic semiring of a language.
[57]
On context-free languages and push-down automata - ScienceDirect
This note describes a special type of one-way, one-tape automata in the sense of Rabin and Scott that idealizes some of the elementary formal features used
[58]
Semiring Parsing - SpringerLink
In this chapter an application of semiring theory in parsing (a.k.a.”semiring parsing”) will be introduced. A semiring parsing framework is proposed and studied ...
[59]
[PDF] Methods and Applications of (max,+) Linear Algebra
This semiring is commutative (a b = b a), idempotent (a a = a), and non zero elements have an inverse for (we call semifields the semirings that satisfy this ...
[60]
[PDF] On Radicals of Semirings and Related Problems - arXiv
Jun 7, 2012 · And a hemiring R is a semiring if its multiplicative semigroup (R, ·) actually is a monoid (R, ·, 1) with identity element 1. Any hemiring R.<|separator|>
[61]
Power Algebras over Semirings
### Summary of Relevant Content on Hemirings and Incidence Algebras
[62]
[PDF] SEMIGROUP NEAR-RINGS by JDP Meldrum - University of York
A near-ring is a generalization of a ring where two axioms are omitted: addition is not necessarily abelian and only one distributive law holds. Definition 1.1.
[63]
From Nearrings and Nearfields to K-Loops - SpringerLink
One of the strongest impulses in the area of nearrings and nearfields started at a Hamburg. In 1934 HANS ZASSENHAUS(28.05.
[64]
[PDF] Representation of Near-Semirings and Approximation of ... - IIT Delhi
This work observes that S-semigroups are essentially the representations of near-semirings to proceed to establish categorical representation of near-semirings.
[65]
The algebraic characterizations for a formal power series over ...
Mar 10, 2016 · A strong bimonoid is a more general structure that can be viewed as a semiring where the distributivity assumption is dropped. All semirings are ...
[66]
[PDF] Weighted Finite Automata over Strong Bimonoids
Sep 24, 2009 · In semirings, by definition, the multiplication operation is distributive over addition and this was crucial for almost all of the theory ...
[67]
Higher categories and semirings - MathOverflow
May 20, 2011 · Similarly, semirings can be thought of as the collection of all endomorphisms of a commutative monoid. Now there is an unmistakable resemblence ...
[68]
[2401.04242] Automata and coalgebras in categories of species
Jan 8, 2024 · ... linear species (introduced by Leroux to study combinatorial ... Category Theory (math.CT); Formal Languages and Automata Theory (cs.FL).
[69]
On $L$-fuzzy ideals in semirings. II - EuDML
Neggers, Joseph, Jun, Young Bae, and Kim, Hee Sik. "On $L$-fuzzy ideals in semirings. II." Czechoslovak Mathematical Journal 49.1 (1999): 127-133. <http://eudml ...Missing: seminal | Show results with:seminal
[70]
[PDF] BASIC CONCEPTS OF ENRICHED CATEGORY THEORY
Reprints in Theory and Applications of Categories, No. 10, 2005. BASIC CONCEPTS OF. ENRICHED CATEGORY THEORY. G.M. KELLY, F.A.A.. PROFESSOR OF ...