The EMS Publishing House is now EMS Press and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

Journal of the European Mathematical Society


Full-Text PDF (260 KB) | Metadata | Table of Contents | JEMS summary
Online access to the full text of Journal of the European Mathematical Society is restricted to the subscribers of the journal, who are encouraged to communicate their IP-address(es) to their agent or directly to the publisher at
subscriptions@ems-ph.org
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