Journal of the European Mathematical Society
Full-Text PDF (260 KB) | Metadata | Table of Contents | JEMS summary
Published online: 2018-04-23
Finitely related algebras in congruence modular varieties have few subpowersLibor Barto (1) Charles University, Prague, Czechia
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.
Keywords: Finitely related algebra, congruence modular variety, Gumm terms, few subpowers, cube terms
Barto Libor: Finitely related algebras in congruence modular varieties have few subpowers. J. Eur. Math. Soc. 20 (2018), 1439-1471. doi: 10.4171/JEMS/790