On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers

This paper shows that the collection of identities in two variables which hold in the algebra N of the natural numbers with constant zero, and binary operations of sum and maximum does not have a finite equational axiomatization. This gives an alternative proof of the non-existence of a finite basis for N--a result previously obtained by the authors. As an application of the main theorem, it is shown that the language of Basic Process Algebra (over a singleton set of actions), with or without the empty process, has no finite equational axiomatization modulo trace equivalence

Abstract: