The max-plus algebra of the natural numbers has no finite equational basis
✍ Scribed by Luca Aceto; Zoltán Ésik; Anna Ingólfsdóttir
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 206 KB
- Volume
- 293
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
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 ÿnitely 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 o ered. 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.