Low growth equational complexity

DOI10.1017/S0013091518000354MaRDI QIDQ5228210zbMATH OpenOpenAlexWikidataFDO

Authors Marcel Jackson

Publication date 9 August 2019

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

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

zbMATH Keywords

groupscomplexityvarietiesequationsquasi-identity

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(3)

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

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)