Galois connections, consistency and propagation for constraint solvers with abstract data types
COM1 Level 3
MR1, COM1-03-19
Abstract:
Traditional constraint solvers provide a framework to declaratively specify and solve problems over variables that can take values within finite domains (typically finite sets of integers). A key component in a modern constraint solver are propagators for global constraints. A propagator prunes the search space by removing partial solutions that cannot be extended to a full solution.
For abstract domains such as strings of unknown length, it is not clear what propagators can and should prune. In this talk I will introduce a framework inspired by abstract interpretation that allows us to specify what propagation means in a concrete implementation of an abstract domain. This is based on join work with Joseph Scott.
Biodata:
Justin Pearson (http://user.it.uu.se/~justin/) is a senior lecturer (docent) at Uppsala University, Sweden. He is a member of the optimisation research group (http://www.it.uu.se/research/group/optimisation) His research is primary on constraint programming, local search, and its applications.