Open AccessOn the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers
Author(s) -
Luca Aceto,
Zoltán Ésik,
Anna Ingólfsdóttir
Publication year - 1999
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v6i22.20079
Subject(s) - mathematics , modulo , natural number , trace (psycholinguistics) , combinatorics , equivalence (formal languages) , singleton , mathematics subject classification , discrete mathematics , algebra over a field , pure mathematics , pregnancy , philosophy , linguistics , biology , genetics
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.