Journal of the European Mathematical Society


Full-Text PDF (260 KB) | Metadata | Table of Contents | JEMS summary
Volume 20, Issue 6, 2018, pp. 1439–1471
DOI: 10.4171/JEMS/790

Published online: 2018-04-23

Finitely related algebras in congruence modular varieties have few subpowers

Libor Barto[1]

(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