03941nam a22006015i 4500001001800000003000900018005001700027007001500044008004100059020003700100024003500137050001700172072001500189072002300204082001500227245016300242264008200405300003400487336002600521337002600547338003600573347002400609490005800633505053400691520130301225650002202528650002602550650004002576650001602616650003502632650002902667650002302696650002202719650002802741650004702769650002102816650004602837650004602883650002302929700003002952700003402982700003203016710003403048773002003082776003603102830005803138856004803196912001403244912001403258942001203272950003803284999001703322978-3-540-92800-3DE-He21320170515111656.0cr nn 008mamaa100301s2008 gw | s |||| 0|eng d a97835409280039978-3-540-92800-37 a10.1007/978-3-540-92800-32doi 4aQA76.6-76.66 7aUM2bicssc 7aCOM0510002bisacsh04a005.1122310aComplexity of Constraintsh[electronic resource] :bAn Overview of Current Research Themes /cedited by Nadia Creignou, Phokion G. Kolaitis, Heribert Vollmer. 1aBerlin, Heidelberg :bSpringer Berlin Heidelberg :bImprint: Springer,c2008. aVII, 321 p.bonline resource. atextbtxt2rdacontent acomputerbc2rdamedia aonline resourcebcr2rdacarrier atext filebPDF2rda1 aLecture Notes in Computer Science,x0302-9743 ;v52500 aBoolean Constraint Satisfaction Problems: When Does Postâ€™s Lattice Help? -- Basics of Galois Connections -- Recent Results on the Algebraic Approach to the CSP -- Dualities for Constraint Satisfaction Problems -- A Logical Approach to Constraint Satisfaction -- Uniform Constraint Satisfaction Problems and Database Theory -- Constraint Satisfaction Problems with Infinite Templates -- Partial Polymorphisms and Constraint Satisfaction Problems -- to the Maximum Solution Problem -- Present and Future of Practical SAT Solving. aNowadays constraint satisfaction problems (CSPs) are ubiquitous in many different areas of computer science, from artificial intelligence and database systems to circuit design, network optimization, and theory of programming languages. Consequently, it is important to analyze and pinpoint the computational complexity of certain algorithmic tasks related to constraint satisfaction. The complexity-theoretic results of these tasks may have a direct impact on, for instance, the design and processing of database query languages, or strategies in data-mining, or the design and implementation of planners. This state-of-the-art survey contains the papers that were invited by the organizers after conclusion of an International Dagstuhl-Seminar on Complexity of Constraints, held in Dagstuhl Castle, Germany, in October 2006. A number of speakers were solicited to write surveys presenting the state of the art in their area of expertise. These contributions were peer-reviewed by experts in the field and revised before they were collated to the 9 papers of this volume. In addition, the volume contains a reprint of a survey by Kolaitis and Vardi on the logical approach to constraint satisfaction that first appeared in 'Finite Model Theory and its Applications', published by Springer in 2007. 0aComputer science. 0aComputer programming. 0aData structures (Computer science). 0aAlgorithms. 0aComputer sciencexMathematics. 0aArtificial intelligence. 0aComputer graphics.14aComputer Science.24aProgramming Techniques.24aAlgorithm Analysis and Problem Complexity.24aData Structures.24aDiscrete Mathematics in Computer Science.24aArtificial Intelligence (incl. Robotics).24aComputer Graphics.1 aCreignou, Nadia.eeditor.1 aKolaitis, Phokion G.eeditor.1 aVollmer, Heribert.eeditor.2 aSpringerLink (Online service)0 tSpringer eBooks08iPrinted edition:z9783540927990 0aLecture Notes in Computer Science,x0302-9743 ;v525040uhttp://dx.doi.org/10.1007/978-3-540-92800-3 aZDB-2-SCS aZDB-2-LNC 2ddccEB aComputer Science (Springer-11645) c18427d18427