Existence of cube terms in finite algebras

DOI10.1007/S00012-020-00700-7zbMATH Open1498.08006arXiv1901.04975OpenAlexW3120170916MaRDI QIDQ2226982FDOQ2226982

Authors: Alexandr Kazda, D. N. Zhuk 

Publication date: 9 February 2021

Published in: Algebra Universalis (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (11)

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

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)