Equational theories of tropical semirings

DOI10.1016/S0304-3975(02)00864-2zbMath1021.08002OpenAlexW2106855117MaRDI QIDQ1874279

Luca Aceto, Anna Ingólfsdóttir, Zoltán Ésik

Publication date: 25 May 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00864-2

zbMATH Keywords

convexityequational logicvarietiescomplete axiomatizationsexponential time complexitytropical semiringscommutative idempotent weak semiringsrelative axiomatizations

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Algebraic theory of languages and automata (68Q70) Semirings (16Y60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Equational classes, universal algebra in model theory (03C05)

Related Items (5)

Axiomatizing rational power series over natural numbers ⋮ Analysis of linear systems over idempotent semifields ⋮ On the maximal solution of a linear system over tropical semirings ⋮ Up-To Techniques for Weighted Systems ⋮ Solving linear systems over tropical semirings through normalization method and its applications

Cites Work

• Limitedness theorem on finite automata with distance functions
• On the topological structure of a finitely generated semigroup of matrices
• Algorithms for determining relative star height and star height
• Linear and combinatorial optimization in ordered algebraic structures
• Complete systems of \(\mathcal B\)-rational identities
• Minimax algebra
• Some consequences of a Fatou property of the tropical semiring
• A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring
• The max-plus algebra of the natural numbers has no finite equational basis
• Regular languages of star height one
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• Methods and applications of (max,+) linear algebra
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Equational theories of tropical semirings