ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS

DOI10.1142/S0218196709004956zbMath1172.08004MaRDI 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 algebra; tame congruence theory; congruence modularity; idempotent algebra; polynomial-time algorithms; Mal'tsev conditions; congruence distributivity; congruence permutable; EXPTIME-complete

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

08B05: Equational logic, Mal'tsev conditions

08B10: Congruence modularity, congruence distributivity

Related Items

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

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