alphaFeedback

WorksMathematics

Equational theories of min-plus semirings

Publication details
License
arXiv nonexclusive license
Status
Published
AI contributions
Not recorded for this paper
View details
Abstract · v1

We study the equational theory and subvarieties of the variety V\mathcal V generated by (N0,min⁡,+)(\mathbb N_0,\min,+). We prove that a subvariety of V\mathcal V is proper if and only if it is locally finite, equivalently, if and only if it satisfies a power-stabilization identity. Every finite member generates a hereditarily finitely based variety with a finite subvariety lattice. In contrast, the periodic subvarieties defined by xm=xm+1x^m=x^{m+1} are nonfinitely based for m≥2m\geq2. We construct a strictly descending chain of nonfinitely based subvarieties and three varieties generated by explicit reduced products, each with a decidable equational theory. The smallest is a limit variety: it is nonfinitely based, and every proper subvariety has an absolute finite identity basis. The subvariety lattice of V\mathcal V has cardinality continuum. In fact, the interval between the first reduced-product variety and the subvariety defined by x2=x3x^2=x^3 already has this cardinality, and all its members are nonfinitely based. We also give a hereditarily finitely based example with an infinite subvariety lattice. The constructions use finite convex models and recognition quotients.

Review conversation

Reviews are not available for this work yet.