Polynomial-time tests for difference terms in idempotent varieties

DOI10.1142/S021819671950036XMaRDI QIDQ5237442zbMATH OpenWikidataFDO

Authors William Demeo, Ralph Freese, Matthew Valeriote

Publication date 18 October 2019

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitydifference termidempotent algebraMaltsev conditiontame congruence theory

Mathematics Subject Classification ID

Computational methods for problems pertaining to general algebraic systems (08-08) Structure theory of algebraic structures (08A05) Equational logic, Mal'tsev conditions (08B05) Congruence modularity, congruence distributivity (08B10) Analysis of algorithms and problem complexity (68Q25)

Abstract: We consider the following practical question: given a finite algebra A in a finite language, can we efficiently decide whether the variety generated by A has a difference term? We answer this question (positively) in the idempotent case and then describe algorithms for constructing difference term operations.

Recommendations

• Simpler Maltsev conditions for (weak) difference terms in locally finite varieties
• Varieties with a difference term
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• Existence of cube terms in finite algebras
• Deciding the existence of minority terms

Cites work

• A finite basis theorem for difference-term varieties with a finite residual bound
• A Subalgebra Intersection Property for Congruence Distributive Varieties
• Computational complexity of various Mal'cev conditions
• Computing congruences efficiently
• scientific article; zbMATH DE number 4035895 (Why is no real title available?)
• scientific article; zbMATH DE number 139656 (Why is no real title available?)
• Idempotent n-permutable varieties.
• Modularity prevents tails
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• Simpler Maltsev conditions for (weak) difference terms in locally finite varieties
• The Relationship Between Two Commutators
• The shape of congruence lattices
• The structure of finite algebras
• Varieties having Boolean factor congruences
• Varieties with a difference term

Cited in

(4)

• Simpler Maltsev conditions for (weak) difference terms in locally finite varieties
• Characterizing the commutator in varieties with a difference term
• Local–global property for G-invariant terms
• Superassociative structures of terms and formulas defined by transformations preserving a partition

This page was built for publication: Polynomial-time tests for difference terms in idempotent varieties

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