This HTML5 document contains 45 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n18http://localhost/temp/predkladatel/
n20http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n9http://linked.opendata.cz/resource/domain/vavai/projekt/
n13http://linked.opendata.cz/resource/domain/vavai/subjekt/
n10http://linked.opendata.cz/ontology/domain/vavai/
n16http://linked.opendata.cz/resource/domain/vavai/zamer/
n12http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216208%3A11320%2F12%3A10127443%21RIV13-GA0-11320___/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
rdfshttp://www.w3.org/2000/01/rdf-schema#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n8http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n6http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n17http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n11http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n4http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n19http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n14http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n22http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216208%3A11320%2F12%3A10127443%21RIV13-GA0-11320___
rdf:type
skos:Concept n10:Vysledek
rdfs:seeAlso
http://dx.doi.org/10.2168/LMCS-8(1:07)2012
dcterms:description
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. 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.
dcterms:title
ABSORBING SUBALGEBRAS, CYCLIC TERMS, AND THE CONSTRAINT SATISFACTION PROBLEM ABSORBING SUBALGEBRAS, CYCLIC TERMS, AND THE CONSTRAINT SATISFACTION PROBLEM
skos:prefLabel
ABSORBING SUBALGEBRAS, CYCLIC TERMS, AND THE CONSTRAINT SATISFACTION PROBLEM ABSORBING SUBALGEBRAS, CYCLIC TERMS, AND THE CONSTRAINT SATISFACTION PROBLEM
skos:notation
RIV/00216208:11320/12:10127443!RIV13-GA0-11320___
n10:predkladatel
n13:orjk%3A11320
n3:aktivita
n11:P n11:Z
n3:aktivity
P(GP201/09/P223), Z(MSM0021620839)
n3:cisloPeriodika
1
n3:dodaniDat
n22:2013
n3:domaciTvurceVysledku
n20:6798268
n3:druhVysledku
n14:J
n3:duvernostUdaju
n17:S
n3:entitaPredkladatele
n12:predkladatel
n3:idSjednocenehoVysledku
120798
n3:idVysledku
RIV/00216208:11320/12:10127443
n3:jazykVysledku
n4:eng
n3:klicovaSlova
absorbing subalgebra; cyclic term; Taylor variety; Constraint Satisfaction Problem
n3:klicoveSlovo
n6:Taylor%20variety n6:Constraint%20Satisfaction%20Problem n6:absorbing%20subalgebra n6:cyclic%20term
n3:kodStatuVydavatele
DE - Spolková republika Německo
n3:kontrolniKodProRIV
[104468D36C60]
n3:nazevZdroje
Logical Methods in Computer Science
n3:obor
n19:BA
n3:pocetDomacichTvurcuVysledku
1
n3:pocetTvurcuVysledku
2
n3:projekt
n9:GP201%2F09%2FP223
n3:rokUplatneniVysledku
n22:2012
n3:svazekPeriodika
8
n3:tvurceVysledku
Barto, Libor Kozik, Marcin
n3:wos
000302505000007
n3:zamer
n16:MSM0021620839
s:issn
1860-5974
s:numberOfPages
27
n8:doi
10.2168/LMCS-8(1:07)2012
n18:organizacniJednotka
11320