Seminar:

     A Systematic Approach to Propagating Boolean Set Constraints

By:
                              Guido Tack
                    http://www.ps.uni-sb.de/~tack/
                    Department of Computer Science
                     Saarland University, Germany
On:
                    Thursday 11th of December 2008
                        at 11:15 in room 1311
          of http://www.polacksbacken.uu.se/index_itc.shtml

Abstract: 

Boolean set constraints are equations or subset relations between
terms constructed from the Boolean connectives, which are usually
written as union, intersection, and complement for the Boolean algebra
of sets.  Most propagation-based constraint solvers that support set
constraints represent the domains of set variables as intervals
between a lower and an upper bound, in order to avoid representing the
exponential-size full domain.  Propagators for Boolean set constraints
in this set-interval approximation have traditionally been given as
ad-hoc propagation rules for a small number of constraints.

In this talk, I will present a systematic technique for deriving
strong set-interval propagators for Boolean set constraints from
formal specifications of the constraints.  I will discuss the run-time
complexity of propagating these constraints, and sketch implementation
techniques based on binary decision diagrams.  Finally, I will clarify
the relation to set constraints specified using monadic second-order
logic.