Outcome of Dagstuhl Seminars: Complexity of Constraints 2008

Nadia Creignou, Phokion G. Kolaitis, Heribert Vollmer (Eds.): Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar]. Lecture Notes in Computer Science 5250 Springer 2008, ISBN 978-3-540-92799-0

Introduction. 1-2
Nadia Creignou, Heribert Vollmer:
Boolean Constraint Satisfaction Problems: When Does Post's Lattice Help?. 3-37
Ferdinand Börner:
Basics of Galois Connections. 38-67
Andrei A. Bulatov, Matthew Valeriote:
Recent Results on the Algebraic Approach to the CSP. 68-92
Andrei A. Bulatov, Andrei A. Krokhin, Benoit Larose:
Dualities for Constraint Satisfaction Problems. 93-124
Phokion G. Kolaitis, Moshe Y. Vardi:
A Logical Approach to Constraint Satisfaction. 125-155
Francesco Scarcello, Georg Gottlob, Gianluigi Greco:
Uniform Constraint Satisfaction Problems and Database Theory. 156-195
Manuel Bodirsky:
Constraint Satisfaction Problems with Infinite Templates. 196-228
Henning Schnoor, Ilka Schnoor:
Partial Polymorphisms and Constraint Satisfaction Problems. 229-254
Peter Jonsson, Gustav Nordh:
Introduction to the Maximum SolutionProblem. 255-282
Oliver Kullmann:
Present and Future of Practical SAT Solving. 283-319