Finitely related algebras in congruence modular varieties have few subpowers (Q1644001)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finitely related algebras in congruence modular varieties have few subpowers |
scientific article |
Statements
Finitely related algebras in congruence modular varieties have few subpowers (English)
0 references
21 June 2018
0 references
Summary: We show that every finite algebra which is finitely related and lies in a congruence modular variety has few subpowers. This result, combined with other theorems, has interesting consequences for the complexity of several computational problems associated to finite relational structures: the constraint satisfaction problem, the primitive positive formula comparison problem, and the learnability problem for primitive positive formulas. Another corollary is that it is decidable whether an algebra given by a set of relations has few subpowers.
0 references
finitely related algebra
0 references
congruence modular variety
0 references
gumm terms
0 references
few subpowers
0 references
cube terms
0 references