The max-plus algebra of the natural numbers has no finite equational basis

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

Review text

Let \({\mathbf N} = (N, \vee , +, 0)\) denote the algebra of the natural numbers equipped with the usual sum operation \(+\), constant \(0\) and the operation \(\vee\) for the maximum of two numbers. In the paper, it is proven that the equational theory of the algebra \({\mathbf N}\) is not finitely based, while the varieties generated by the reducts \((N, +, 0)\) and \((N, \vee, 0)\) of \({\mathbf N}\) have very simple finite equational axiomatizations. Moreover, for any \(n\), the equations in at most \(n\) variables that hold in \({\mathbf N}\) do not form an equational basis. As a stepping stone in the proof of these facts, several results of independent interest are obtained. In particular, explicit descriptions of the free algebras in the variety generated by \({\mathbf N}\) are offered. Such descriptions are based upon a geometric characterization of the equations that hold in \({\mathbf N}\), which also yields that the equational theory of \({\mathbf N}\) is decidable in exponential time.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: The max-plus algebra of the natural numbers has no finite equational basis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1870591)