ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS

DOI10.1142/S0218196709004956zbMath1172.08004OpenAlexW1963602153MaRDI QIDQ3621430

Ralph Freese, Matthew A. Valeriote

Publication date: 21 April 2009

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

Full work available at URL: https://doi.org/10.1142/s0218196709004956

zbMATH Keywords

free algebratame congruence theorycongruence modularityidempotent algebrapolynomial-time algorithmsMal'tsev conditionscongruence distributivitycongruence permutableEXPTIME-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Equational logic, Mal'tsev conditions (08B05) Congruence modularity, congruence distributivity (08B10)

Related Items (27)

The Jónsson distributivity spectrum ⋮ THE DISTRIBUTIVITY SPECTRUM OF BAKER’S VARIETY ⋮ The computational complexity of deciding whether a finite algebra generates a minimal variety ⋮ Local–global property for G-invariant terms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Conservative constraint satisfaction re-revisited ⋮ The Gumm level equals the Alvin level in congruence distributive varieties ⋮ Deciding the Existence of Minority Terms ⋮ Unnamed Item ⋮ The Tschantz and the Alvin higher conditions are equivalent in congruence distributive varieties ⋮ Existence of cube terms in finite algebras ⋮ Testing for a semilattice term ⋮ DECIDING SOME MALTSEV CONDITIONS IN FINITE IDEMPOTENT ALGEBRAS ⋮ On the complexity of the Leibniz hierarchy ⋮ On the CSP Dichotomy Conjecture ⋮ Maltsev families of varieties closed under join or Maltsev product ⋮ Mal'tsev condition satisfaction problems for conditions which imply edge terms ⋮ Unnamed Item ⋮ Deciding absorption ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ Mitschke's theorem is sharp ⋮ Polynomial-time tests for difference terms in idempotent varieties ⋮ Idempotent n -permutable varieties ⋮ COMPUTATIONAL COMPLEXITY OF VARIOUS MAL'CEV CONDITIONS ⋮ Unnamed Item ⋮ Between an n-ary and an n + 1-ary near-unanimity term

Cites Work

• Unnamed Item
• Unnamed Item
• Computing congruences efficiently
• Congruence modularity is permutability composed with distributivity
• A characterization of congruence permutable locally finite varieties
• Problems and results in tame congruence theory. A survey of the '88 Budapest workshop
• Varieties whose congruences satisfy certain lattice identities
• Congruence permutable and congruence 3-permutable locally finite varieties
• On \(n\)-permutable congruences
• A Characterization of Identities Implying Congruence Modularity I
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• FINDING TYPE SETS IS NP-HARD
• The structure of finite algebras
• Modularity prevents tails
• The Relationship Between Two Commutators
• TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
• Algebras Whose Congruence Lattices are Distributive.
• A Characterization of Modularity for Congruence Lattices of Algebras*
• A modification of Polin's variety

This page was built for publication: ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS