Fact-checked by Grok 2 weeks ago

Tropical semiring

The tropical semiring, also known as the min-plus semiring, is a fundamental algebraic structure in tropical mathematics, consisting of the extended real numbers \mathbb{R} \cup \{\infty\} equipped with two operations: tropical addition defined as the minimum \oplus : x \oplus y = \min(x, y), and tropical multiplication defined as ordinary addition \odot : x \odot y = x + y.^[1] This structure forms a commutative semiring where \infty serves as the additive identity (neutral element for \oplus) and 0 as the multiplicative identity (neutral element for \odot), with the operations satisfying associativity, commutativity, and distributivity: x \odot (y \oplus z) = (x \odot y) \oplus (x \odot z).^[2] Unlike classical rings, it lacks additive inverses but features idempotent addition, since x \oplus x = x, making it particularly suited for modeling optimization problems where minima represent choices.^[3] Key properties of the tropical semiring include its zero-sum absorption, where \infty \odot x = \infty for all x, and its extension to variants such as the tropical integers \mathbb{Z} \cup \{\infty\} or rationals \mathbb{Q} \cup \{\infty\} under the same operations.^[3] Polynomials over this semiring evaluate to piecewise-linear concave functions, enabling the tropicalization of classical algebraic geometry into combinatorial structures like tropical curves and hypersurfaces.^[1] These features underpin tropical linear algebra, where matrices and vectors support efficient algorithms for shortest paths in graphs (via min-plus matrix multiplication) and other discrete optimization tasks.^[2] Originally introduced by Imre Simon in the 1970s within automata theory and formal languages to study limited subsets of free monoids, the tropical semiring gained prominence in the 1990s through its "tropical" nomenclature, coined by Dominique Perrin to honor the pioneering work of the Brazilian mathematician Imre Simon.^[3] Its applications span diverse fields, including phylogenetic tree reconstruction in biology—where tropical eigenvalues model tree metrics—and enumerative combinatorics, as well as software implementations for Burnside-type counting issues in group theory.^[2]^[3] Ongoing research leverages tropical semirings for robust approximations in machine learning and optimization, highlighting their role in bridging algebra, geometry, and computation.^[4]

Definition and Properties

Formal Definition

The tropical min semiring consists of the set \mathbb{R} \cup \{+\infty\} equipped with the binary operations of tropical addition \oplus, defined by x \oplus y = \min(x, y) for all x, y \in \mathbb{R} \cup \{+\infty\}, and tropical multiplication \otimes, defined by x \otimes y = x + y. The additive identity (zero) for \oplus is +\infty, satisfying x \oplus (+\infty) = +\infty \oplus x = x, and the multiplicative identity (one) for \otimes is 0, satisfying x \otimes 0 = 0 \otimes x = x. A dual construction is the tropical max semiring on the set \mathbb{R} \cup \{-\infty\}, where \oplus is defined by x \oplus y = \max(x, y) and \otimes by x \otimes y = x + y, with additive identity -\infty and multiplicative identity 0.^[5] The min and max tropical semirings are isomorphic via the negation mapping \phi: \mathbb{R} \cup \{+\infty\} \to \mathbb{R} \cup \{-\infty\} given by \phi(x) = -x (with \phi(+\infty) = -\infty), which interchanges the roles of min and max while preserving addition. Tropical exponentiation by a natural number n is the iterated application of \otimes: x^{(n)} = x \otimes \cdots \otimes x (n times), which equals n \cdot x using standard multiplication. Both the min and max structures satisfy the axioms of a semiring: the operations \oplus and \otimes are associative and commutative, \otimes distributes over \oplus, and the specified identities exist.

Algebraic Properties

The tropical semiring, typically defined over the set \mathbb{R} \cup \{+\infty\} with addition \oplus as the minimum operation and multiplication \otimes as standard addition, exhibits idempotence in its additive structure: for all x \in \mathbb{R} \cup \{+\infty\}, x \oplus x = \min(x, x) = x.^[1] This property distinguishes it from classical rings, rendering the semiring idempotent and enabling applications in combinatorial optimization where repeated minima do not alter outcomes.^[6] Unlike classical rings, the tropical semiring lacks additive inverses: for any finite a \in \mathbb{R}, there exists no x such that x \oplus a = +\infty.^[1] The element +\infty serves as the additive identity (zero) for \oplus, satisfying +\infty \oplus a = a \oplus +\infty = a for all a, while also acting as the multiplicative absorbing element (zero) since +\infty \otimes a = +\infty + a = +\infty for all a.^[6] This absorption ensures that operations involving +\infty propagate through expressions without reversal, a feature rooted in the non-negativity of the underlying reals. The multiplicative operation \otimes endows \mathbb{[R](/page/R)} \cup \{+\infty\} with the structure of a commutative monoid isomorphic to (\mathbb{R}, +, [0](/page/0)), where 0 is the multiplicative identity since [0](/page/0) \otimes a = a for all a.^[1] Moreover, the semiring has no zero divisors beyond the absorbing element: if a \otimes b = +\infty, then either a = +\infty or b = +\infty, preserving the integrity of finite products.^[6] Tropical polynomials are formal expressions of the form p(x) = a_0 \oplus a_1 \otimes x \oplus \cdots \oplus a_n \otimes x^{\otimes n}, where x^{\otimes k} = k \otimes x denotes repeated multiplication, evaluated as \min_i (a_i + i x) for inputs x \in \mathbb{R}.^[1] These polynomials yield piecewise-linear concave functions, with "roots" corresponding to points where the minimum is achieved by at least two terms, forming the corner locus—a balanced polyhedral complex of rays and segments.^[7] Newton's diagram provides a geometric tool for analyzing such polynomials, constructed as the convex hull of points (i, a_i) in \mathbb{R}^2, whose lower boundary facets determine the subdivision dual to the corner locus.^[1] The corner locus consists of edges weighted by the gcd of lattice differences between monomials achieving the minimum, with multiplicity defined via the number of integer points on dual segments in the diagram, ensuring the structure balances at vertices.^[7] In the tropical setting, the semiring adapts concepts from valued fields with value group \mathbb{R} (modeled by the tropical semiring) and residue field an algebraically closed field such as \mathbb{C}, possessing characteristic 0 due to the absence of finite-order additive relations beyond the idempotence, akin to the underlying reals, facilitating connections to classical algebraic geometry over fields of characteristic 0 with such residue fields.^[8]

Variants and Generalizations

Min-Plus and Max-Plus Semirings

The min-plus semiring is constructed over the extended real numbers \mathbb{R} \cup \{+\infty\}, equipped with the binary operations of addition defined as a \oplus b = \min(a, b) for all a, b \in \mathbb{R} \cup \{+\infty\} and multiplication defined as a \otimes b = a + b whenever the sum is well-defined, with the additive identity +\infty and multiplicative identity $0.^[9] These operations satisfy the semiring axioms, including distributivity: \min(a, b) + c = \min(a + c, b + c).^[9] This structure models optimization scenarios, particularly shortest path computations in weighted graphs, where the minimum selects the optimal route and addition accumulates edge weights along paths.^[9] For instance, if A represents edge weights between nodes, then powers A^{\otimes n} yield shortest path distances of length up to n.^[10] The max-plus semiring operates on the set \mathbb{[R](/page/R)} \cup \{-\infty\}, with addition a \oplus b = \max(a, b) and multiplication a \otimes b = a + b, where the additive identity is -\infty and the multiplicative identity is $0.^[11] Distributivity holds as \max(a, b) + c = \max(a + c, b + c).^[11] This semiring applies to scheduling problems and control theory, where the maximum identifies critical paths or determines completion times in discrete event systems, such as assembly lines where tasks wait for predecessors.^[12] For example, in project scheduling, matrix operations compute the earliest finish times, with the max operation capturing dependencies along the longest chain of tasks.^[13] The min-plus and max-plus semirings are isomorphic through the order-reversing bijection \phi: \mathbb{R} \cup \{+\infty\} \to \mathbb{R} \cup \{-\infty\} given by \phi(x) = -x (with \phi(+\infty) = -\infty).^[10] This mapping preserves the semiring structure because \phi(\min(a, b)) = \max(\phi(a), \phi(b)), since -\min(a, b) = \max(-a, -b), and \phi(a + b) = - (a + b) = (-a) + (-b) = \phi(a) \otimes \phi(b).^[10] To see this explicitly, consider \phi(a \oplus b) = \phi(\min(a, b)) = -\min(a, b) = \max(-a, -b) = \max(\phi(a), \phi(b)) = \phi(a) \oplus_{\max} \phi(b), and similarly for multiplication.^[10] Literature conventions favor the min-plus semiring in optimization due to its alignment with minimization objectives like shortest paths, while the max-plus semiring predominates in control theory for modeling timed systems and critical path analysis.^[9]^[12] Both variants exhibit shared algebraic properties, such as idempotence of addition (a \oplus a = a).^[9] Tropical matrix multiplication exemplifies these operations; in the min-plus semiring, for matrices A, B \in (\mathbb{R} \cup \{+\infty\})^{m \times n}, the product is defined entrywise as (A \otimes B)_{ij} = \min_{k} (A_{ik} + B_{kj}), interpreting the result as the minimum cost over intermediate indices k.^[9] In the max-plus case, (A \otimes B)_{ij} = \max_{k} (A_{ik} + B_{kj}) computes the maximum over paths, as in longest path problems.^[10] For a simple 2x2 example in min-plus, if A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} and B = \begin{pmatrix} 5 & 6 \\ 7 & 8 \end{pmatrix}, then (A \otimes B)_{11} = \min(1+5, 2+7) = \min(6, 9) = 6.^[9]

Broader Tropical Structures

Tropical matrix semirings extend the operations of the tropical semiring to matrices over the set \mathbb{R} \cup \{+\infty\}, where addition is defined as the minimum and multiplication as standard addition. The matrix addition is entrywise minimum, while the min-plus matrix product of two matrices A and B has entries given by (A \otimes B)_{ij} = \min_k (A_{ik} + B_{kj}). This structure preserves the semiring properties and is particularly useful in dynamic programming, such as computing all-pairs shortest paths in graphs, where the (n-1)-th power of the adjacency matrix yields the minimum costs.^[14] Finite tropical semirings are constructed over finite totally ordered sets, such as \{0, 1, \dots, n-1\} \cup \{\infty\} equipped with minimum as addition and a form of modular addition as multiplication, often derived from quotients of the natural numbers tropical semiring. For instance, the semiring M_r = \mathbb{N} / (r \sim \infty) identifies multiples of r with infinity, enabling modular arithmetic within the tropical framework while maintaining associativity and distributivity. These structures arise in automata theory and formal languages, where they model rational series and solve decidability problems like the finite prefix problem.^[3] Supertropical semirings generalize the tropical setting by incorporating a layer of "ghost" elements alongside tangible ones, typically over an ordered monoid like \mathbb{R} \cup \{-\infty\}, with maximum as addition and standard addition as multiplication. Ghost elements, which are equivalence classes of tangible values under a ghost map \nu, allow for a finer distinction in algebraic identities and avoid the loss of information inherent in pure tropical idempotence. Axioms include supertropicality (ensuring ghosts behave appropriately under operations) and bipotence (idempotence up to ghosts), enabling advanced structure theory such as polynomial factorization into linear factors. This extension provides a more robust foundation for algebraic geometry, supporting analogs of classical results like the Nullstellensatz.^[15] Tropical semirings fit within broader algebraic frameworks as special cases of dioids and quantales. A dioid is an idempotent semiring where addition satisfies a \oplus a = a, making the tropical (min-plus) semiring a commutative dioid with a natural partial order induced by the operations. Quantales extend this to complete lattices with suprema-distributing multiplication, encompassing tropical structures when infinite joins are considered, as in the power set of languages under union and concatenation. These generalizations unify tropical algebra with optimization and concurrency models.^[16]^[17] In tropical geometry, varieties are defined as the sets in \mathbb{R}^n where tropical polynomials "vanish," meaning the minimum in the tropical expression p(x) = \bigoplus c_i x^{a_i} = \min_i (c_i + \langle a_i, x \rangle) is attained at least twice among the terms. These zero sets form balanced polyhedral complexes, with facets corresponding to the Newton polytope's regular subdivisions induced by the coefficients. The polyhedral structure equips tropical varieties with combinatorial properties, such as dual fans, facilitating the study of classical algebraic varieties via their degenerations.^[18]

Connections to Algebra and Analysis

Relation to Valued Fields

A valuation on a field K is a map v: K \to \mathbb{R} \cup \{\infty\} such that v(0) = \infty, v(ab) = v(a) + v(b) for all a, b \in K, and v(a + b) \geq \min(v(a), v(b)) for all a, b \in K.^[19] This structure captures the notion of "size" or "order of vanishing" in non-Archimedean settings, where the inequality reflects a hierarchy of magnitudes stricter than the usual triangle inequality.^[19] The process of tropicalization associates to such a valued field K the image v(K), which forms a subsemiring of the tropical semiring (\mathbb{R} \cup \{\infty\}, \min, +).^[19] Specifically, the additive structure of the value group \Gamma = v(K^\times) (an ordered abelian subgroup of (\mathbb{R}, +)) aligns with the tropical multiplication (ordinary addition), while the non-Archimedean inequality ensures compatibility with tropical addition (minimum), as \min(v(a), v(b)) \leq v(a + b).^[20] This embedding models how algebraic operations in K degenerate into piecewise-linear structures in the tropical setting, bridging field theory to idempotent analysis.^[19] Examples illustrate this connection concretely. The trivial valuation on \mathbb{Q} or \mathbb{C}, defined by v(x) = 0 for x \neq 0 and v(0) = \infty, yields the image \{0, \infty\}, a minimal subsemiring where \min(0, 0) = 0 and $0 + 0 = 0.^[19] In contrast, the p-adic valuation on the field \mathbb{Q}_p (for a prime p) assigns to a nonzero element its exponent of p in the factorization, producing the image \mathbb{Z} \cup \{\infty\}, closed under minimum and addition.^[20] Ostrowski's theorem classifies all non-trivial absolute values on \mathbb{Q} (equivalently, their associated valuations), showing they are either the trivial one, p-adic for some prime p, or the archimedean absolute value (which does not satisfy the non-Archimedean inequality).^[21] The residue field and value group further highlight how the tropical semiring encodes the field's decomposition. The residue field is the quotient \mathcal{O}_K / \mathfrak{m}, where \mathcal{O}_K = \{x \in K \mid v(x) \geq 0\} is the valuation ring and \mathfrak{m} = \{x \in K \mid v(x) > 0\} the maximal ideal; it captures the "units modulo infinitesimals."^[19] Meanwhile, the value group \Gamma provides the additive backbone, with the tropical semiring \Gamma \cup \{\infty\} under \min and + preserving the ordered additive structure of \Gamma, thus modeling the field's scaling behavior tropically.^[20] In non-Archimedean fields, the strict triangle inequality v(a + b) \geq \min(v(a), v(b))—with equality when v(a) \neq v(b)—induces idempotent addition in the value semigroup, as the minimum operation dominates unequal terms exactly, mirroring the tropical semiring's idempotence \min(\gamma, \gamma) = \gamma.^[19] This property underpins the rigidity of tropical limits from valued fields, facilitating applications in non-Archimedean geometry.^[20]

Idempotent and Log Semirings

Idempotent semirings are algebraic structures in which the addition operation satisfies a \oplus a = a for all elements a, making them a subclass of semirings with commutative and associative addition that distributes over multiplication. These structures generalize classical rings by lacking additive inverses, and the tropical semiring serves as a canonical example, where addition is the minimum (or maximum) operation and multiplication is standard addition over the extended reals \mathbb{R} \cup \{\infty\}.^[22] The max-plus algebra, an isomorphic variant of the tropical semiring using maximum for addition, exemplifies idempotent semirings and arises in optimization contexts like shortest path problems.^[22] Log semirings provide an analytic bridge to tropical structures through limiting processes. Consider the family of semirings S_h = (\mathbb{R} \cup \{-\infty\}, \oplus_h, \odot_h) where \oplus_h(u, v) = h \ln(e^{u/h} + e^{v/h}) and \odot_h(u, v) = u + v; as h \to 0^+, \oplus_h converges to the maximum operation, yielding the max-plus tropical semiring, while h \to 0^- yields the min-plus version.^[23] This logarithmic transformation, applied to positive reals, deforms classical arithmetic into idempotent tropical limits, preserving key algebraic relations like distributivity.^[23] Maslov dequantization formalizes this transition from quantum or classical settings to tropical mathematics by taking limits as a parameter (analogous to Planck's constant) approaches zero, often via imaginary values, resulting in idempotent semirings. In this process, traditional addition and multiplication deform into tropical operations, maintaining idempotence (a \oplus a = a) and enabling analysis of asymptotic behaviors in optimization and geometry.^[23] The dequantization preserves structural properties, such as the equivalence between polynomial equations over fields and piecewise-linear functions over tropical semirings.^[23] Tropical semirings relate closely to Kleene algebras, which axiomatize operations on formal languages: union (as idempotent addition), concatenation (multiplication), and Kleene star (iteration). In the tropical setting, matrix powers over the min-plus semiring model path weights in automata, and Kleene's theorem equates rational languages (closed under these operations) with recognizable languages accepted by finite automata, where tropical arithmetic computes minimal costs or lengths.^[3] This connection allows tropical methods to decide finiteness properties of rational languages by reducing to semigroup problems over the tropical semiring.^[3] Unlike classical rings, which support subtraction and yield eigenvalues via determinants, tropical semirings lack negatives, precluding direct analogs; instead, a tropical eigenvalue \lambda for a matrix A satisfies A \otimes x = \lambda \oplus x for some nonzero x, interpreted as a min-plus eigenvector where \lambda is the minimal cycle mean in graph terms. Irreducible matrices possess a unique eigenvalue, contrasting with the potentially multiple eigenvalues in classical linear algebra, and eigenvectors are positive (no infinities) without zeros.^[24] This framework supports optimization problems, such as finding minimal-cost assignments, via spectral properties.^[24]

History and Applications

Historical Development

The origins of tropical semirings trace back to early developments in idempotent analysis and max-plus algebra during the mid-20th century. In the 1960s, V. P. Maslov initiated work on optimization problems that laid foundational ideas for idempotent structures, particularly in the context of variational methods and control theory, which later evolved into idempotent analysis in the 1970s and 1980s. Independently, in 1963, N. N. Vorob'ev introduced concepts of extremal matrix algebra, an early precursor to max-plus algebra, focusing on optimization over ordered sets.^[25] These efforts were extended in the 1970s by researchers like R. A. Cuninghame-Green, who applied min-max path problems to production scheduling, further solidifying the algebraic framework.^[26] The term "tropical semiring" was coined in the 1990s by Dominique Perrin to honor the pioneering work of the Brazilian mathematician Imre Simon, whose research in the 1970s on finite semirings and automata theory had pioneered applications of these structures in computer science.^[3] Simon's 1978 paper on limited subsets of free monoids notably employed min-plus structures on the natural numbers extended by infinity to model piecewise-linear functions, influencing subsequent min-plus models in theoretical computing.^[27] Simon, based in Brazil for much of his career, contributed seminal results on semigroup theory and automata, bridging algebra and formal languages during the 1970s.^[28] Key milestones in the 1980s included the application of max-plus algebra to automatic control systems, particularly through the study of max-plus automata for modeling discrete-event systems like timed Petri nets and scheduling.^[29] This period saw growing interest in nonexpansive mappings and linear systems over max-plus structures, as surveyed in foundational works on the dynamics of such algebras.^[26] In the 1990s, tropical geometry began to take shape, with Grigory Mikhalkin developing connections between amoebas of algebraic varieties and piecewise-linear objects, setting the stage for enumerative applications.^[30] The 2000s marked a surge in tropical semiring research, fueled by arXiv preprints and dedicated conferences, such as the 2007 Oberwolfach Workshop on Tropical Geometry, which highlighted its geometric potential.^[31] Similarly, the Loughborough Workshop on Tropical Geometry in April 2007 fostered discussions on matroids and linear spaces over these semirings.^[32] Post-2010, tropical semirings integrated deeply with mirror symmetry and enumerative geometry, as exemplified in programs linking tropical degenerations to Calabi-Yau manifolds and Gromov-Witten invariants. This era emphasized tropical methods in proving mirror symmetry conjectures, including the Strominger-Yau-Zaslow framework.

Applications in Mathematics and Beyond

Tropical semirings find significant applications in optimization, where the min-plus structure facilitates efficient computation of shortest paths in graphs through matrix powers that analogize the Floyd-Warshall algorithm.^[33] This approach leverages the tropical semiring's operations to model path lengths, enabling the identification of minimal costs without explicit enumeration of all routes.^[33] Additionally, tropical linear programming extends classical methods to idempotent settings, solving feasibility and optimization problems over ordered semirings by tropicalizing the simplex algorithm.^[34] In tropical geometry, these semirings underpin enumerative invariants, such as counting plane curves of given degree passing through generic points, achieved via correspondences between classical complex curves and their tropical limits defined by amoebas and Newton polytopes.^[35] This framework equates the number of complex curves satisfying intersection conditions to the number of tropical curves through specified points in the plane, providing combinatorial tools for otherwise intractable enumerative problems.^[35] Furthermore, tropical varieties arise as degenerations of algebraic varieties over non-Archimedean valued fields, linking tropical geometry to broader algebraic structures and enabling the study of geometric invariants under valuation.^[36] Control theory employs max-plus variants of tropical semirings to model timed Petri nets through automata that capture synchronization and timing constraints in discrete event systems.^[37] These max-plus automata represent the behavior of safe timed Petri nets, preserving temporal properties for analysis and verification.^[37] In scheduling applications, the max-plus eigenvalue of system matrices determines asymptotic cycle times, facilitating the design of periodic schedules that optimize throughput in production and transportation networks.^[38] Phylogenetics utilizes tropical linear algebra to reconstruct tree metrics from distance matrices, where the tropical rank of a matrix corresponds to the dimension of the phylogenetic tree space it realizes.^[2] This approach checks the additive tree structure of evolutionary distances, completing partial matrices to consistent tree representations via tropical convex hulls.^[2] In physics, tropical semirings emerge in semiclassical approximations through Maslov dequantization, which interprets the classical limit as an idempotent structure where the Maslov index tracks phase corrections in path integrals over Lagrangian manifolds.^[39] This dequantization bridges quantum mechanics to tropical mathematics, reformulating semiclassical propagators in min-plus terms for asymptotic analysis.^[39] In economics, tropical models support resource allocation by framing transportation problems as matrix optimizations in idempotent semirings, minimizing costs in supply-demand networks akin to shortest-path formulations.^[40] Computer science applies tropical weights to minimize weighted automata recognizing regular languages, where the semiring structure enables equivalence checks and state reduction via dynamic programming over path weights.^[41] This minimization preserves the language's weighted acceptance while reducing computational complexity for parsing and recognition tasks.^[41] More recently, as of 2024, tropical semirings have been integrated into machine learning through semiring activations in neural networks, enabling algorithmic reasoning for combinatorial optimization problems.^[42] In cryptography, tropical schemes for public-key encryption have emerged since 2013, with ongoing developments in 2023-2024 leveraging idempotent structures for secure computations.^[43]

References

[1]
[PDF] Tropical mathematics
It simply stands for the French view of Brazil. 1 Arithmetic. Our basic object of study is the tropical semiring (R ∪ {∞}, ⊕, ⊙) ...
[2]
[PDF] Tropical mathematics - Berkeley Math
If n = 1 and C = R≥0, this is the tropical semiring. Develop linear algebra and algebraic geometry over these semirings, and implement efficient software for ...
[3]
[PDF] Tropical Semirings - Jean-Eric Pin - HAL
All these semirings are called tropical semirings. Other extensions include the tropical integers Z = (Z ∪ {∞}, min, +), the tropical rationals Q = (Q ∪ {∞}, ...
[4]
[PDF] Max-plus algebra - CMAP
Properly speaking, it refers to the tropical semiring, which is the subsemiring of Rmin consisting of the elements in N ∪ {+∞}. The completed max-plus semiring ...
[5]
[PDF] Tropical Semirings - l'IRIF
The zero is a zero for the second law : for all s ∈ k, 0s = s0 = 0. A semiring is commutative if its multiplication is commutative. Rings are the first examples ...
[6]
None
### Summary of Newton's Diagram for Tropical Polynomials (Allman, Tropical Plane Curves and Tropical Intersection Theory, 2013)
[7]
[PDF] Introduction to Tropical Geometry
Nov 4, 2009 · This is a very preliminary and incomplete draft of the forthcoming textbook on tropical geometry by Diane Maclagan and Bernd Sturmfels.
[8]
[PDF] Min-plus algebraic low rank matrix approximation - arXiv
Aug 23, 2017 · Min-plus algebra is the study of equations that are structured around the binary operations 'taking the minimum' and 'plus'. More formally min- ...
[9]
[PDF] Linear regression over the max-plus semiring - arXiv
Dec 10, 2017 · By studying the max-plus algebraic properties of the matrix M we can now predict the behavior of the system, for example computing its leading ...
[10]
[PDF] On max-plus two-sided linear systems whose solution sets are min ...
Feb 12, 2024 · They were later solved algebraically by introducing a type of dual semiring with two operators: a ⊕′ b := min(a, b) and a ⊗′ b := a + b [15].
[11]
Analysis and control of max-plus linear discrete-event systems
Dec 2, 2019 · Although network calculus is originally based on min-plus algebra, alternative formulations can be developed based on max-plus algebra ( ...
[12]
[PDF] An Algebraic Approach to Project Schedule Development ... - arXiv
Oct 24, 2012 · We use this semiring as the basis for the development of algebraic solu- tions to project scheduling problems in the subsequent sections. 2.2 ...
[13]
[PDF] 451: Dynamic Programming II - Carnegie Mellon University
Sep 8, 2020 · Here is a slightly exotic structure, the min-plus semiring, aka the tropical ... multiplication over the min-plus semiring. Claim: Ak(u, v) ...Missing: product | Show results with:product
[14]
[PDF] arXiv:0806.1171v3 [math.AC] 7 Dec 2009
Dec 7, 2009 · Our overall objective is to cover the max-plus algebra by an algebraic structure that we call the supertropical semiring, which has a more ...
[15]
[PDF] An Introduction to Idempotency - Inria
A dioid, or idempotent semiring, is a semiring, D, such that: • a + a = a for all a ED. A commutative dioid is one in which a.b = b.a for all a, bED. A dioid is ...
[16]
[PDF] Graphs, Dioids and Semirings : New Models and Algorithms
... dioids such as Min-Plus or Max-Plus dioids are sometimes referred to as. Tropical semirings (see for example Simon 1994). 6.8. Product of Dioids. Given p dioids ...
[17]
[PDF] Tropical Geometry - arXiv
Aug 19, 2019 · Tropical curves, and more generally tropical varieties, are geometric shapes that can be defined by familiar equations called polynomials.
[18]
[PDF] On Basic Concepts of Tropical Geometry
Tropical addition of p-adic numbers. The construction of Subsection 2.11 admits a modification that can be applied to any field with non-Archimedean valuation.
[19]
[PDF] arXiv:2301.05483v4 [math.RA] 4 Jun 2024
Jun 4, 2024 · Abstract. The symmetrized tropical semiring is an extension of the tropical semifield, initially in- troduced to solve tropical linear ...
[20]
[PDF] Keith Conrad - OSTROWSKI FOR NUMBER FIELDS
Ostrowski classified nontrivial absolute values on Q as p-adic and archimedean. This extends to number fields K, with p-adic, real, and complex absolute values.
[21]
Idempotent and tropical mathematics; complexity of algorithms and ...
The semifield is a typical example of an idempotent semiring; this is a semiring with idempotent addition, i.e., x ⊕ x = x for arbitrary element of this ...
[22]
None
### Summary of Log Semirings, Limits to Tropical Semirings, and Maslov Dequantization
[23]
Extremal properties of tropical eigenvalues and solutions to tropical ...
Mar 1, 2015 · The eigenvectors of irreducible matrices have no zero components and so are regular. Reducible matrices may possess several eigenvalues. The ...
[24]
Subadditivity, Generalized Products of Random Matrices ... - SIAM.org
N. N. Vorob'ev, An extremal matrix algebra, Dokl. Akad. Nauk SSSR, 152 ... Memory Loss Property for Products of Random Matrices in the Max-Plus Algebra.
[25]
From max-plus algebra to nonexpansive mappings: a nonlinear ...
In this paper, we survey the development of such a theory, based on the dynamics of maps which are nonexpansive in the ℓ∞ norm. This has its origins in linear ...
[26]
[PDF] Tropical Mathematics - arXiv
Aug 7, 2004 · The adjective “tropical” was coined by French mathematicians, including. Jean-Eric Pin [19], in the honor of their Brazilian colleague Imre ...
[27]
Limited subsets of a free monoid - ACM Digital Library
Browse by Title · Proceedings · SFCS '78 · Limited subsets of a free monoid. Article. Share on. Limited subsets of a free monoid. Author: Imre Simon. Imre Simon.
[28]
The influence of Imre Simon's work in the theory of automata ...
Jan 31, 2019 · The purpose of this tribute is to review three major results due to Simon that had a considerable influence on the development of automata and semigroup theory.
[29]
Max-plus algebra in the history of discrete event systems
Aug 6, 2025 · This paper is a survey of the history of max-plus algebra and its role in the field of discrete event systems during the last three decades.
[30]
Amoebas of Algebraic Varieties and Tropical Geometry - SpringerLink
Mikhalkin, Enumerative tropical geometry in R 2, http://arxiv.org math.AG/0312530. G. Mikhalkin, Maximal real algebraic hypersurfaces (in preparation).
[31]
Workshops 2007 - Mathematisches Forschungsinstitut Oberwolfach
0750 - Tropical Geometry . [OWR-2007-57] Workshop Report 2007,57 (2007) - (09 Dec - 15 Dec 2007). Tropical Geometry is a new and rapidly ...
[32]
[PDF] Workshop on Tropical Geometry
Workshop on Tropical Geometry. Loughborough University. 21–23 April 2007. Abstracts. E.M. Feichtner (Stuttgart). Bergman fans of matroids and tropical ...
[33]
[PDF] Semiring Frameworks and Algorithms for Shortest-Distance Problems
The semi- ring (R+ ∪ {∞}, min, +, ∞, 0) is the underlying algebraic structure of many classical shortest-paths algorithms and is called the tropical semiring.
[34]
[PDF] tropicalizing the simplex algorithm - CMAP
Introduction. The tropical semiring (T, ⊕, ) is the set T = R ∪ {−∞} endowed with the two operations a ⊕ b = max(a, b) and a b = a + b. We are.
[35]
[math/0312530] Enumerative tropical algebraic geometry in R2 - arXiv
Dec 31, 2003 · Authors:Grigory Mikhalkin. View a PDF of the paper titled Enumerative tropical algebraic geometry in R2, by Grigory Mikhalkin. View PDF.
[36]
[1108.6126] A guide to tropicalizations - arXiv
Aug 31, 2011 · We generalize basic results from tropical geometry which are well-known for special ground fields to arbitrary non-archimedean valued fields.
[37]
[PDF] Modeling and Analysis of Timed Petri Nets using Heaps of Pieces
Timed safe Petri nets are special (max,+) automata, which compute the height ... Scheduling Theory and Its Applications, Wiley, 1995. [11] C. C erin ...
[38]
Modeling and scheduling of production systems by using max-plus ...
Mar 6, 2023 · In this paper a max-plus formalism is used for the modeling and scheduling of such production systems. Structural decisions such as choosing one ...
[39]
The Maslov dequantization, idempotent and tropical mathematics
Jul 1, 2005 · Tropical mathematics can be treated as a result of the so-called Maslov dequantization of the traditional mathematics over numerical fields as ...Missing: semiring | Show results with:semiring
[40]
[PDF] Semirings in Databases, Automata, and Logic - DROPS
In the transportation problem as studied in the theory of resource allocation in economic theory, a finite set of suppliers seek to distribute their production ...
[41]
[PDF] Minimizing Deterministic Lattice Automata - CS - Huji
4 A “weight-pushing process” is useful also in the minimization of weighted automata over the tropical semiring [19]. 5 Note that, by definition, all the ...