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

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

Abstract

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 characterization of the equations that hold in N, which
also yields that the equational theory of N is decidable in exponential
time.
Published
1999-12-03
How to Cite
Aceto, L., Ésik, Z., & Ingólfsdóttir, A. (1999). The Max-Plus Algebra of the Natural Numbers has no Finite Equational Basis. BRICS Report Series, 6(33). https://doi.org/10.7146/brics.v6i33.20102