Finitely related algebras in congruence modular varieties have few subpowers

Libor Barto

doi:10.4171/jems/790

Geodesic

Parcourir par

Finitely related algebras in congruence modular varieties have few subpowers

Libor Barto

Journal of the European Mathematical Society, Tome 20 (2018) no. 6, pp. 1439-1471.

Voir la notice de l'article provenant de la source EMS Press

Résumé

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.

DOI : 10.4171/jems/790

Classification : 08-XX, 68-XX
Mots-clés : Finitely related algebra, congruence modular variety, Gumm terms, few subpowers, cube terms

@article{JEMS_2018_20_6_a2,
     author = {Libor Barto},
     title = {Finitely related algebras in congruence modular varieties have few subpowers},
     journal = {Journal of the European Mathematical Society},
     pages = {1439--1471},
     publisher = {mathdoc},
     volume = {20},
     number = {6},
     year = {2018},
     doi = {10.4171/jems/790},
     url = {https://geodesic-test.mathdoc.fr/articles/10.4171/jems/790/}
}

TY  - JOUR
AU  - Libor Barto
TI  - Finitely related algebras in congruence modular varieties have few subpowers
JO  - Journal of the European Mathematical Society
PY  - 2018
SP  - 1439
EP  - 1471
VL  - 20
IS  - 6
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/articles/10.4171/jems/790/
DO  - 10.4171/jems/790
ID  - JEMS_2018_20_6_a2
ER  -

%0 Journal Article
%A Libor Barto
%T Finitely related algebras in congruence modular varieties have few subpowers
%J Journal of the European Mathematical Society
%D 2018
%P 1439-1471
%V 20
%N 6
%I mathdoc
%U https://geodesic-test.mathdoc.fr/articles/10.4171/jems/790/
%R 10.4171/jems/790
%F JEMS_2018_20_6_a2

Libor Barto. Finitely related algebras in congruence modular varieties have few subpowers. Journal of the European Mathematical Society, Tome 20 (2018) no. 6, pp. 1439-1471. doi : 10.4171/jems/790. https://geodesic-test.mathdoc.fr/articles/10.4171/jems/790/

Cité par

Steindl, Markus Not all nilpotent monoids are finitely related, Algebra Universalis, Volume 85 (2024) no. 1, p. 18 (Id/No 13) | DOI:10.1007/s00012-023-00841-5 | Zbl:1540.20120
Barto, Libor; Brady, Zarathustra; Bulatov, Andrei; Kozik, Marcin; Zhuk, Dmitriy Unifying the three algebraic approaches to the CSP via minimal Taylor algebras, TheoretiCS, Volume 3 (2024), p. 76 (Id/No 14) | DOI:10.46298/theoretics.24.14 | Zbl:7875518
Lipparini, Paolo Between an $n$ -ary and an $n + 1$ -ary near-unanimity term, International Journal of Algebra and Computation, Volume 32 (2022) no. 8, pp. 1595-1614 | DOI:10.1142/s0218196723500017 | Zbl:1509.08002
Gillibert, Pierre; Jonušas, Julius; Kompatscher, Michael; Mottet, Antoine; Pinsker, Michael When symmetries are not enough: a hierarchy of hard constraint satisfaction problems, SIAM Journal on Computing, Volume 51 (2022) no. 2, pp. 175-213 | DOI:10.1137/20m1383471 | Zbl:1483.68141
Barto, Libor; Brady, Zarathustra; Bulatov, Andrei; Kozik, Marcin; Zhuk, Dmitriy Minimal Taylor algebras as a common framework for the three algebraic approaches to the CSP, Proceedings of the 2021 36th annual ACM/IEEE symposium on logic in computer science, LICS 2021, Rome, Italy, June 29 – July 2, 2021, Piscataway, NJ: IEEE Press, 2021, p. 13 (Id/No 54) | DOI:10.1109/lics52264.2021.9470557 | Zbl:1553.08009
Gillibert, Pierre; Jonušas, Julius; Pinsker, Michael Pseudo-loop conditions, Bulletin of the London Mathematical Society, Volume 51 (2019) no. 5, pp. 917-936 | DOI:10.1112/blms.12286 | Zbl:1444.08003
Chen, Hubie; Valeriote, Matthew Learnability of solutions to conjunctive queries, Journal of Machine Learning Research (JMLR), Volume 20 (2019), p. 28 (Id/No 67) | Zbl:1489.68114
Moore, Matthew Finite degree clones are undecidable, Theoretical Computer Science, Volume 796 (2019), pp. 237-271 | DOI:10.1016/j.tcs.2019.09.014 | Zbl:1454.08002
Gyenizse, Gergő; Maróti, Miklós Quasiorder lattices of varieties, Algebra Universalis, Volume 79 (2018) no. 2, p. 17 (Id/No 38) | DOI:10.1007/s00012-018-0512-1 | Zbl:1397.08001
Dolinka, Igor Finite bands are finitely related, Semigroup Forum, Volume 97 (2018) no. 1, pp. 115-130 | DOI:10.1007/s00233-017-9897-y | Zbl:1400.20056
Barto, Libor; Bulín, Jakub Deciding absorption in relational structures, Algebra Universalis, Volume 78 (2017) no. 1, pp. 3-18 | DOI:10.1007/s00012-017-0440-5 | Zbl:1412.08004
Barto, Libor; Krokhin, Andrei; Willard, Ross Polymorphisms, and how to use them, The constraint satisfaction problem: complexity and approximability, Dagstuhl seminar 15301, July 2015, Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik, 2017, pp. 1-44 | DOI:10.4230/dfu.vol7.15301.1 | Zbl:1482.68161
Barto, Libor; Kozik, Marcin Absorption in universal algebra and CSP, The constraint satisfaction problem: complexity and approximability, Dagstuhl seminar 15301, July 2015, Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik, 2017, pp. 45-77 | DOI:10.4230/dfu.vol7.15301.45 | Zbl:1482.68160
Jackson, Marcel; Kowalski, Tomasz; Niven, Todd Complexity and polymorphisms for digraph constraint problems under some basic constructions, International Journal of Algebra and Computation, Volume 26 (2016) no. 7, pp. 1395-1433 | DOI:10.1142/s0218196716500600 | Zbl:1401.05132
Bulatov, Andrei A. Graphs of relational structures: restricted types, Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5–8, 2016, New York, NY: Association for Computing Machinery (ACM), 2016, pp. 642-651 | DOI:10.1145/2933575.2933604 | Zbl:1401.68112

Cité par 15 documents. Sources : zbMATH