ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
From MaRDI portal
Publication:3621430
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
free algebra; tame congruence theory; congruence modularity; idempotent algebra; polynomial-time algorithms; Mal'tsev conditions; congruence distributivity; congruence permutable; EXPTIME-complete
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