Existence of cube terms in finite algebras
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10438457" target="_blank" >RIV/00216208:11320/21:10438457 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=0H.d4Pj-Js" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=0H.d4Pj-Js</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00012-020-00700-7" target="_blank" >10.1007/s00012-020-00700-7</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Existence of cube terms in finite algebras
Popis výsledku v původním jazyce
We study the problem of whether a given finite algebra with finitely many basic operations contains a cube term; we give both structural and algorithmic results. We show that if such an algebra has a cube term then it has a cube term of dimension at most N, where the number N depends on the arities of basic operations of the algebra and the size of the basic set. For finite idempotent algebras we give a tight bound on N that, in the special case of algebras with more than ((vertical bar A vertical bar)(2)) basic operations, improves an earlier result of K. Kearnes and a. Szendrei. On the algorithmic side, we show that deciding the existence of cube terms is in P for idempotent algebras and in EXPTIME in general. Since an algebra contains a k-ary near unanimity operation if and only if it contains a k-dimensional cube term and generates a congruence distributive variety, our algorithm also lets us decide whether a given finite algebra has a near unanimity operation.
Název v anglickém jazyce
Existence of cube terms in finite algebras
Popis výsledku anglicky
We study the problem of whether a given finite algebra with finitely many basic operations contains a cube term; we give both structural and algorithmic results. We show that if such an algebra has a cube term then it has a cube term of dimension at most N, where the number N depends on the arities of basic operations of the algebra and the size of the basic set. For finite idempotent algebras we give a tight bound on N that, in the special case of algebras with more than ((vertical bar A vertical bar)(2)) basic operations, improves an earlier result of K. Kearnes and a. Szendrei. On the algorithmic side, we show that deciding the existence of cube terms is in P for idempotent algebras and in EXPTIME in general. Since an algebra contains a k-ary near unanimity operation if and only if it contains a k-dimensional cube term and generates a congruence distributive variety, our algorithm also lets us decide whether a given finite algebra has a near unanimity operation.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2021
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Algebra Universalis
ISSN
0002-5240
e-ISSN
—
Svazek periodika
82
Číslo periodika v rámci svazku
1
Stát vydavatele periodika
CH - Švýcarská konfederace
Počet stran výsledku
29
Strana od-do
11
Kód UT WoS článku
000610553000002
EID výsledku v databázi Scopus
2-s2.0-85099356936