On the equational complexity of RRA

DOI10.1007/S00012-012-0210-3MaRDI QIDQ1935010zbMATH OpenOpenAlexFDO

Authors Jeremy F. Alm

Publication date 30 January 2013

Published in Algebra Universalis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.2092

zbMATH Keywords

equational complexityrepresentable relation algebras

Mathematics Subject Classification ID

Cylindric and polyadic algebras; relation algebras (03G15) Equational logic, Mal'tsev conditions (08B05)

Abstract: We prove that the equational complexity function for the variety of representable relation algebras is bounded below by a log-log function.

Review text

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. \]

Recommendations

• EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM
• There is no finite-variable equational axiomatization of representable relation algebras over weakly representable relation algebras
• Complexity of equations valid in algebras of relations. II: Finite axiomatizations
• scientific article; zbMATH DE number 150219
• Low growth equational complexity

Cites work

• Axiomatizability of reducts of algebras of relations
• EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM
• scientific article; zbMATH DE number 67032 (Why is no real title available?)
• On representable relation algebras
• Relation algebras and projective geometries
• Relation algebras by games
• The Nonexistence of Certain Finite Projective Planes
• Weakly representable but not representable relation algebras
• Weakly representable relation algebras form a variety

Cited in

(2)

• Low growth equational complexity
• There is no finite-variable equational axiomatization of representable relation algebras over weakly representable relation algebras

This page was built for publication: On the equational complexity of RRA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1935010)