The Max-Plus Algebra of the Natural Numbers has no Finite Equational Basis

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

October 1999


This paper shows that the collection of identities which hold in the algebra N of the natural numbers with constant zero, and binary operations of sum and maximum is not finitely based. Moreover, it is proven that, for every $n$, the equations in at most $n$ variables that hold in 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 N are offered. Such descriptions are based upon a geometric characterisation of the equations that hold in N, which also yields that the equational theory of N is decidable in exponential time

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.