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

## DOI:

https://doi.org/10.7146/brics.v6i22.20079## Abstract

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 omega-complete equational

axiomatization modulo trace equivalence.

AMS Subject Classification (1991): 08A70, 08B05, 03C05, 68Q70.

ACM Computing Classification System (1998): F.4.1.

Keywords and Phrases: Equational logic, varieties, complete axiomatizations,

process algebra, trace equivalence.

## Downloads

## Published

## How to Cite

*BRICS Report Series*,

*6*(22). https://doi.org/10.7146/brics.v6i22.20079

## Issue

## Section

## License

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.