Existence of cube terms in finite algebras

DOI10.1007/S00012-020-00700-7MaRDI QIDQ2226982zbMATH OpenOpenAlexFDO

Authors Alexandr Kazda, D. N. Zhuk

Publication date 9 February 2021

Published in Algebra Universalis (Search for Journal in Brave)

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

zbMATH Keywords

algorithmcube termidempotent algebranear unanimityfew subpowerscube term blocker

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Equational logic, Mal'tsev conditions (08B05) Operations and polynomials in algebraic structures, primal algebras (08A40)

Abstract: We study the problem of whether a given finite algebra with finitely many basic operations contains a cube term; we give both structural and algorithmic results. We show that if such an algebra has a cube term then it has a cube term of dimension at most $N$, where the number $N$ depends on the arities of basic operations of the algebra and the size of the basic set. For finite idempotent algebras we give a tight bound on $N$ that, in the special case of algebras with more than $$ basic operations, improves an earlier result of K. Kearnes and A. Szendrei. On the algorithmic side, we show that deciding the existence of cube terms is in P for idempotent algebras and in EXPTIME in general. Since an algebra contains a $k$-ary near unanimity operation if and only if it contains a $k$-dimensional cube term and generates a congruence distributive variety, our algorithm also lets us decide whether a given finite algebra has a near unanimity operation.

Recommendations

• Finitely related clones and algebras with cube terms.
• Cube term blockers without finiteness
• The existence of a near-unanimity term in a finite algebra is decidable
• Finitely related algebras in congruence distributive varieties have near unanimity terms
• On the (un)decidability of a near-unanimity term

Cites work

• scientific article; zbMATH DE number 1096962 (Why is no real title available?)
• Closed systems of functions and predicates
• Computational complexity of various Mal'cev conditions
• Cube term blockers without finiteness
• Deciding absorption
• Finitely related clones and algebras with cube terms.
• Key (critical) relations preserved by a weak near-unanimity function
• Near-unanimity is decomposable
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• The existence of a near-unanimity term in a finite algebra is decidable
• Tractability and learnability arising from algebras with few subpowers
• Varieties with few subalgebras of powers

Cited in

(11)

• Polynomial-time tests for difference terms in idempotent varieties
• What can be expected from a cubic derivation on finite dimensional algebras?
• scientific article; zbMATH DE number 1445631 (Why is no real title available?)
• Naturally dualizable algebras omitting types 1 and 5 have a cube term
• Between an n-ary and an n + 1-ary near-unanimity term
• Cube term blockers without finiteness
• Finitely related clones and algebras with cube terms.
• Deciding the existence of minority terms
• Congruence modularity implies cyclic terms for finite algebras
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• Finite degree clones are undecidable

This page was built for publication: Existence of cube terms in finite algebras

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