Caterpillar duality for constraint satisfaction problems

被引：7

作者：

Carvalho, Catarina ^{[1
]}

Dalmau, Victor ^{[2
]}

Krokhin, Andrei ^{[1
]}

机构：

[1] Univ Durham, Durham DH1 3LE, England

[2] Univ Pompeu Fabra, Barcelona 08003, Spain

来源：

TWENTY-THIRD ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS | 2008年

基金：

英国工程与自然科学研究理事会;

关键词：

HOMOMORPHISMS;

D O I：

10.1109/LICS.2008.19

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The study of constraint satisfaction problems definable in various fragments of Datalog has recently gained considerable importance. We consider constraint satisfaction problems that are definable in the smallest natural recursive fragment of Datalog - monadic linear Datalog with at most one EDB per rule. We give combinatorial and algebraic characterisations of such problems, in terms of caterpillar dualities and lattice operations, respectively. We then apply our results to study graph H-colouring problems.

引用

页码：307 / +

页数：3

共 25 条

[1] [Anonymous], 2006, HDB CONSTRAINT PROGR
[2] ATSERIAS A, 2008, EUROPEAN J IN PRESS
[3] BARTO L, 2008, STOC 08 IN PRESS
[4] BULATOV A, 2008, SURVEYS COM IN PRESS
[5] H-Coloring dichotomy revisited
Bulatov, AA
[J]. THEORETICAL COMPUTER SCIENCE, 2005, 349 (01) : 31 - 39
[6] Dalmau V, 1999, LECT NOTES COMPUT SC, V1713, P159
[7] LINEAR DATALOG AND BOUNDED PATH DUALITY OF RELATIONAL STRUCTURES
Dalmau, Victor
[J]. LOGICAL METHODS IN COMPUTER SCIENCE, 2005, 1 (01)
[8] Ebbinghaus H. D., 1999, Finite Model Theory
[9] Symmetric Datalog and constraint satisfaction problems in logspace
Egri, Laszlo
Larose, Benoit
Tesson, Pascal
[J]. 22ND ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 2007, : 193 - +
[10] List homomorphisms to reflexive graphs
Feder, T
Hell, P
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1998, 72 (02) : 236 - 250

← 1 2 3 →