The max-plus algebra of the natural numbers has no finite equational basis (Q1870591): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Zoltán Ésik / rank | |||
Property / reviewed by | |||
Property / reviewed by: Leonid Matveevich Martynov / rank | |||
Property / author | |||
Property / author: Zoltán Ésik / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Leonid Matveevich Martynov / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4501538 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A menagerie of non-finitely based process semantics over BPA* – from ready simulation to completed traces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4525274 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3951525 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bisimulation can't be traced / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3934450 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5639639 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The variety of Kleene algebras with conversion is not finitely based / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonfinite axiomatizability of the equational theory of shuffle / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4082296 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4200260 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bisimulation through probabilistic testing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Identities in Two-Valued Calculi / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Equational Bases for Lattice Theories. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A field guide to equational logic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5534915 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3050481 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Identical relations in finite groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3907077 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3818127 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4128733 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0304-3975(02)00236-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2080117016 / rank | |||
Normal rank |
Latest revision as of 09:45, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The max-plus algebra of the natural numbers has no finite equational basis |
scientific article |
Statements
The max-plus algebra of the natural numbers has no finite equational basis (English)
0 references
14 May 2003
0 references
Let \({\mathbf N} = (N, \vee , +, 0)\) denote the algebra of the natural numbers equipped with the usual sum operation \(+\), constant \(0\) and the operation \(\vee\) for the maximum of two numbers. In the paper, it is proven that the equational theory of the algebra \({\mathbf N}\) is not finitely based, while the varieties generated by the reducts \((N, +, 0)\) and \((N, \vee, 0)\) of \({\mathbf N}\) have very simple finite equational axiomatizations. Moreover, for any \(n\), the equations in at most \(n\) variables that hold in \({\mathbf 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 \({\mathbf N}\) are offered. Such descriptions are based upon a geometric characterization of the equations that hold in \({\mathbf N}\), which also yields that the equational theory of \({\mathbf N}\) is decidable in exponential time.
0 references
equational logic
0 references
varieties
0 references
complete axiomatizations
0 references
exponential time complexity
0 references
0 references