The Max-Plus Algebra of the Natural Numbers has no Finite Equational Basis

Forfattere

  • Luca Aceto
  • Zoltán Ésik
  • Anna Ingólfsdóttir

DOI:

https://doi.org/10.7146/brics.v6i33.20102

Resumé

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.

Downloads

Publiceret

1999-12-03

Citation/Eksport

Aceto, L., Ésik, Z., & Ingólfsdóttir, A. (1999). The Max-Plus Algebra of the Natural Numbers has no Finite Equational Basis. BRICS Report Series, 6(33). https://doi.org/10.7146/brics.v6i33.20102

Nummer

Nr. 33 (1999): RS-33 The Max-Plus Algebra of the Natural Numbers has no Finite Equational Basis

Sektion

Artikler

Licens

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    1. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  1. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).