On the equational complexity of RRA (Q1935010)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the equational complexity of RRA |
scientific article |
Statements
On the equational complexity of RRA (English)
0 references
30 January 2013
0 references
The \textit{length} of an equation is the total number of operation symbols and variables appearing in the equation. The \textit{equational complexity} of a variety of finite signature \(V\) is the function \(\beta_V :\mathbb{N}\to \mathbb{N}\) defined as follows: \(\beta_V (m)\) is the least integer \(N\) such that for any algebra \(A\) of the similarity class of \(V\) with \(|A|\leq m\), \(A\in V\), if and only if \(A\) satisfies all equations true in \(V\) of length at most \(N\). In this paper, the author considers the variety RRA of representable relation algebra and shows as a main result that for all \(m\geq 2^8\) we have \[ \beta_{\mathrm{RRA}} (m) > 2 \log_2 3 \cdot (\log_3 (\frac{1}{2}\log_2(m) -1)-2) -2. \] Furthermore, the author introduces the function \(\beta^{\ast}_V\) of the equational complexity function with domain the number of atoms of a finite algebra (rather than its cardinality) and shows that \[ \beta^{\ast}_{\mathrm{RRA}} (M) > 2 \log_2 3\cdot [\log_3(M/2-1)-2]-2. \]
0 references
representable relation algebras
0 references
equational complexity
0 references