Galois connections, consistency and propagation for constraint solvers with abstract data types

Dr Justin Pearson, Senior Lecturer, Uppsala University
Chaired by
Dr YAP Hock Chuan, Roland, Associate Professor, School of Computing

  18 Mar 2019 Monday, 10:30 AM to 12:00 PM

 MR1, COM1-03-19


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.


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.