Bridging Constraint Satisfaction and Boolean Satisfiability

• Main Author: Petke, Justyna (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Cham : Springer International Publishing : Imprint: Springer, 2015.
• Edition: 1st ed. 2015.
• Series: Artificial Intelligence: Foundations, Theory, and Algorithms,
• Subjects: Computer science.; Computers.; Artificial intelligence.; Computer Science.; Artificial Intelligence (incl. Robotics).; Theory of Computation.

This book provides a significant step towards bridging the areas of Boolean satisfiability and constraint satisfaction by answering the question why SAT-solvers are efficient on certain classes of CSP instances which are hard to solve for standard constraint solvers. The author also gives theoretica...

Table of Contents:

• Introduction
• Background
• Solver Performance on Tractable CSPs: Empirical Evaluation
• SAT Encodings
• From CSP to SAT: Width Restrictions
• From CSP to SAT: Language Restrictions
• SAT Encodings of a Classical Problem: A Case Study
• Conclusions.    .