Low growth equational complexity

DOI10.1017/S0013091518000354zbMATH Open1441.08002arXiv1607.07156OpenAlexW2506806038WikidataQ129190728 ScholiaQ129190728MaRDI QIDQ5228210FDOQ5228210

Authors: Marcel Jackson 

Publication date: 9 August 2019

Published in: Proceedings of the Edinburgh Mathematical Society (Search for Journal in Brave)

Abstract: The equational complexity function $$ of an equational class of algebras $mathscrV$ bounds the size of equation required to determine membership of $n$-element algebras in $mathscrV$. Known examples of finitely generated varieties $mathscrV$ with unbounded equational complexity have growth in $Omega(n^c)$, usually for $cgeqfrac12$. We show that much slower growth is possible, exhibiting $O(lo{g}_2^3(n))$ growth amongst varieties of semilattice ordered inverse semigroups and additive idempotent semirings. We also examine a quasivariety analogue of equational complexity, and show that a finite group has polylogarithmic quasi-equational complexity function, bounded if and only if all Sylow subgroups are abelian.

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

Recommendations

• EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM
• The equational complexity of Lyndon's algebra
• On the equational complexity of RRA
• Classification in finite model theory: counting finite algebras
• On Computational Complexity of Semilinear Varieties

zbMATH Keywords

groupscomplexityvarietiesequationsquasi-identity

Mathematics Subject Classification ID

Equational logic, Mal'tsev conditions (08B05) Varieties and pseudovarieties of semigroups (20M07)

Cites Work

• Identical relations in finite groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Varieties of groups
• On pseudovarieties
• Title not available (Why is that?)
• The \(\mathfrak q\)-theory of finite semigroups.
• Algebraic point lattices of quasivarieties
• Short presentations for finite groups
• EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM
• Flat algebras and the translation of universal Horn logic to equational logic
• Title not available (Why is that?)
• Inverse Monoids With a Natural Semilattice Ordering
• Conditional identities in finite groups
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• Title not available (Why is that?)
• THE MEMBERSHIP PROBLEM IN FINITE FLAT HYPERGRAPH ALGEBRAS
• The equational complexity of Lyndon's algebra
• Representability is not decidable for finite relation algebras
• REFLEXIVE RELATIONS, EXTENSIVE TRANSFORMATIONS AND PIECEWISE TESTABLE LANGUAGES OF A GIVEN HEIGHT
• On the foundations of inverse monoids and inverse algebras
• A 2EXPTIME complete varietal membership problem
• IDENTITIES IN THE ALGEBRA OF PARTIAL MAPS
• SOME INDECOMPOSABLE VARIETIES OF GROUPS

Cited In (3)

• Nonfinitely based ai-semirings with finitely based semigroup reducts
• On the equational complexity of RRA
• On Computational Complexity of Semilinear Varieties

This page was built for publication: Low growth equational complexity

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