Finitely related algebras in congruence modular varieties have few subpowers

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10383371" target="_blank" >RIV/00216208:11320/18:10383371 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4171/JEMS/790" target="_blank" >https://doi.org/10.4171/JEMS/790</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4171/JEMS/790" target="_blank" >10.4171/JEMS/790</a>

Result language
angličtina
Original language name
Finitely related algebras in congruence modular varieties have few subpowers
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

Project
<a href="/en/project/GA13-01832S" target="_blank" >GA13-01832S: General algebra and its connections to computer science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)