Since 2014
On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers
|
|
| Creator |
Aceto, Luca
Ésik, Zoltán Ingólfsdóttir, Anna |
|
| Description |
This paper shows that the collection of identities in two variableswhich hold in the algebra N of the natural numbers with constantzero, and binary operations of sum and maximum does not have afinite equational axiomatization. This gives an alternative proof of thenon-existence of a finite basis for N - a result previously obtained bythe authors. As an application of the main theorem, it is shown thatthe language of Basic Process Algebra (over a singleton set of actions),with or without the empty process, has no finite omega-complete equationalaxiomatization 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.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
1999-01-22
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/20079
10.7146/brics.v6i22.20079 |
|
| Source |
BRICS Report Series; No 22 (1999): RS-22 On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers
BRICS Report Series; No 22 (1999): RS-22 On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/20079/17705
|
|
| Rights |
Copyright (c) 2015 BRICS Report Series
|
|