SAT Encoding and CSP Reduction for Interconnected Alldiff Constraints
| Titre | SAT Encoding and CSP Reduction for Interconnected Alldiff Constraints |
| Type de publication | Communication |
| Type | Communication avec actes dans un congrès |
| Année | 2009 |
| Langue | Anglais |
| Date du colloque | 2009/01/01 |
| Titre du colloque | 8th Mexican International Conference on Artificial Intelligence, MICAI 2009 |
| Titre des actes ou de la revue | Advances in Artificial Intelligence |
| Volume | 5845 |
| Pagination | 360 - 371 |
| Auteur | Lardeux, Frédéric , Monfroy, Eric, Saubion, Frédéric , Crawford, Broderick, Castro, Carlos |
| Pays | Mexique |
| Editeur | Springer |
| Ville | Guanajuato |
| ISBN | 978-3-642-05257-6 / 978-3-642-05258-3 |
| Mots-clés | Artificial Intelligence (incl. Robotics), Computer Imaging, Vision, Pattern Recognition and Graphics, Data Mining and Knowledge Discovery, image processing and computer vision, pattern recognition, Simulation and Modeling |
| Résumé en anglais | Constraint satisfaction problems (CSP) or Boolean satisfiability problem (SAT) are two well known paradigm to model and solve combinatorial problems. Modeling and resolution of CSP is often strengthened by global constraints (e.g., Alldiff constraint). This paper highlights two different ways of handling specific structural information: a uniform propagation framework to handle (interleaved) Alldiff constraints with some CSP reduction rules; and a SAT encoding of these rules that preserves the reduction properties of CSP. |
| Notes | Date du colloque : 11/2009 |
| URL de la notice | http://okina.univ-angers.fr/publications/ua4479 |
| DOI | 10.1007/978-3-642-05258-3_32 |
| Lien vers le document en ligne |