[Date Prev][Date Next][Date Index]

Korrektur Talk Announcement: Constraints, complexity and clones, by Peter Jeavons

The Database & Artificial Intelligence Group of the Information Systems Institute
invites to the following talk:

Peter Jeavons
Oxford University

Date: Monday December 5, 2005

Time:  11:30 - 12:30

Place: Seminarroom 184/2 (DBAI), Favoritenstraße 9-11/1842, 3rd floor
(when you leave the elevator turn left, go through the corridor, the entrance is on the right side)

Title: Constraints, complexity and clones



This talk will present the general framework of constraint satisfaction from
several different perspectives. This framework can be used to express many
different computational problems, from timetabling to circuit design and
database queries. The complexity of constraint satisfaction problems varies
depending on the forms of the constraints allowed, and we describe a very
successful  approach to determining the complexity of a problem based on the
algebraic properties of the constraints. Using this approach we show that
some very general classes of constraints are tractable. Finally we discuss
how this algebraic approach can be extended to soft constraints, where each
tuple of values is associated with some cost and the problem is to find an
assignment which minimizes the overall cost. For these problems too we show
that there are tractable cases which can be characterized by algebraic