ABSORBING SUBALGEBRAS, CYCLIC TERMS, AND THE CONSTRAINT SATISFACTION PROBLEM

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10127443" target="_blank" >RIV/00216208:11320/12:10127443 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.2168/LMCS-8(1:07)2012" target="_blank" >http://dx.doi.org/10.2168/LMCS-8(1:07)2012</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.2168/LMCS-8(1:07)2012" target="_blank" >10.2168/LMCS-8(1:07)2012</a>

Jazyk výsledku

angličtina

Název v původním jazyce

ABSORBING SUBALGEBRAS, CYCLIC TERMS, AND THE CONSTRAINT SATISFACTION PROBLEM

Popis výsledku v původním jazyce

The Algebraic Dichotomy Conjecture states that the Constraint Satisfaction Problem over a fixed template is solvable in polynomial time if the algebra of polymorphisms associated to the template lies in a Taylor variety, and is NP-complete otherwise. This paper provides two new characterizations of finitely generated Taylor varieties. The first characterization is using absorbing subalgebras and the second one cyclic terms. These new conditions allow us to reprove the conjecture of Bang-Jensen and Hell(proved by the authors) and the characterization of locally finite Taylor varieties using weak near-unanimity terms (proved by McKenzie and Maroti) in an elementary and self-contained way.

Název v anglickém jazyce

ABSORBING SUBALGEBRAS, CYCLIC TERMS, AND THE CONSTRAINT SATISFACTION PROBLEM

Popis výsledku anglicky

The Algebraic Dichotomy Conjecture states that the Constraint Satisfaction Problem over a fixed template is solvable in polynomial time if the algebra of polymorphisms associated to the template lies in a Taylor variety, and is NP-complete otherwise. This paper provides two new characterizations of finitely generated Taylor varieties. The first characterization is using absorbing subalgebras and the second one cyclic terms. These new conditions allow us to reprove the conjecture of Bang-Jensen and Hell(proved by the authors) and the characterization of locally finite Taylor varieties using weak near-unanimity terms (proved by McKenzie and Maroti) in an elementary and self-contained way.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GP201%2F09%2FP223" target="_blank" >GP201/09/P223: Splnitelnost omezujících podmínek a univerzální algebra</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2012

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ů

Název periodika

Logical Methods in Computer Science

ISSN

1860-5974

e-ISSN

—

Svazek periodika

8

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

27

Strana od-do

1-26

Kód UT WoS článku

000302505000007

EID výsledku v databázi Scopus

—