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.