Skip to main content

Research Repository

Advanced Search

Caterpillar duality for constraint satisfaction problems

Carvalho, C.; Dalmau, V.; Krokhin, A.

Caterpillar duality for constraint satisfaction problems Thumbnail


Authors

C. Carvalho

V. Dalmau



Abstract

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.

Citation

Carvalho, C., Dalmau, V., & Krokhin, A. (2008). Caterpillar duality for constraint satisfaction problems. In Twenty-third Annual IEEE Symposium on Logic in Computer Science, 24-27 June 2008, Pittsburgh, PA ; proceedings (307 -316). https://doi.org/10.1109/lics.2008.19

Conference Name 23rd Annual IEEE Symposium on Logic in Computer Science (LICS) 2008
Conference Location Pittsburgh, Pennsylvania
Publication Date Jun 1, 2008
Deposit Date Mar 29, 2010
Publicly Available Date Mar 28, 2024
Pages 307 -316
Series Title LICS '08 Proceedings of the 2008 23rd Annual IEEE Symposium on Logic in Computer Science
Series ISSN 1043-6871
Book Title Twenty-third Annual IEEE Symposium on Logic in Computer Science, 24-27 June 2008, Pittsburgh, PA ; proceedings.
DOI https://doi.org/10.1109/lics.2008.19
Keywords Constraint satisfaction problem, Homomorphism, Duality, Caterpillar structures, Datalog.
Additional Information June 24-June 27, 2008

Files

Published Conference Proceeding (174 Kb)
PDF

Copyright Statement
© 2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.





You might also like



Downloadable Citations