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.
Udgivelsesdato: FEB 3
Udgivelsesdato: FEB 3
Originalsprog | Engelsk |
---|---|
Tidsskrift | Theoretical Computer Science |
Vol/bind | 293 |
Udgave nummer | 1 |
Sider (fra-til) | 169-188 |
ISSN | 0304-3975 |
Status | Udgivet - 2003 |