TITLE: Generating Propagators for Finite Set Constraints
PRESENTER: Christian Schulte, http://web.it.kth.se/~schulte/, email@example.com
AFFILIATION:School of Information and Communication Technology, KTH - Royal Institute of Technology, Sweden, http://web.it.kth.se/
DATE: Monday 3rd July 2006
PLACE: CSE Seminar Room, Level 1, K17
Ideally, programming propagators as implementations of constraints
should be an entirely declarative specification process for a large
class of constraints: a high-level declarative specification is
automatically translated into an efficient propagator.
This talk introduces the use of existential monadic second-order logic
as declarative specification language for finite set propagators.
The approach taken is to automatically derive projection propagators
(involving a single variable only) implementing constraints described
by formulas. By this, we transfer the ideas of indexicals to finite set
constraints while considerably increasing the level of abstraction
available with indexicals. We show soundness and completeness of the
derived propagators and present a runtime analysis, including
techniques for efficiently executing projectors for n-ary constraints.
This is a joint work with:
Guido Tack, Programming Systems Lab, Saarland U, Germany
Gert Smolka, Programming Systems Lab, Saarland U, Germany
BIOGRAPHY OF SPEAKER:
Christian Schulte works as associate professor at the Department of
Electronic, Computer, and Software Systems, School of Information and
Communication Technology, KTH - Royal Institute of Technology in Stockholm,
His research interests include programming languages, in particular
concurrent and constraint-based programming languages, constraint
programming, multi-agent systems, and distributed systems.
Christian has been involved in many international conferences and
workshop in the fields. He has won outstanding awards including
Teacher of the year 2003 for the IT program, KTH, Stockholm,
and the best application paper award, ICLP 2003.
Toby Walsh and Thomas Meyer
Van Hai Ho