Open AccessThe Max-Plus Algebra of the Natural Numbers has no Finite Equational Basis
Author(s) -
Luca Aceto,
Zoltán Ésik,
Anna Ingólfsdóttir
Publication year - 1999
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v6i33.20102
Subject(s) - mathematics , decidability , natural number , basis (linear algebra) , variety (cybernetics) , binary number , constant (computer programming) , zero (linguistics) , discrete mathematics , combinatorics , algebra over a field , pure mathematics , arithmetic , computer science , geometry , statistics , linguistics , philosophy , programming language
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.