|
CS Seminar: Krzysztof Apt, November 27, 2000
- Speaker
-
Prof. Krzysztof Apt,
Centre for Mathematics and Computer Science,
Amsterdam, The Netherlands,
and
Department of Mathematics and Computer Sciences,
University of Amsterdam.
- Date and Time
-
Monday, November 27, 2000 at 15:00
- Place
-
Sala Riunioni,
Dipartimento di Matematica,
Università di Parma,
Via D'Azeglio 85/A,
I-43100 Parma
- Title
-
Constraint Propagation Revisited
- Abstract
-
Constraint propagation lies at the core of constraint processing and
new constraint propagation algorithms keep appearing. In this talk we
show how the constraint propagation process can be explained in simple
and general terms of computing the least common fixpoint of a set of
monotonic and inflationary functions on a partial order. This allows
us to demonstrate that several constraint propagation algorithms
proposed in the literature are in fact instances of generic iteration
algorithms. In particular, we show that correctness of the celebrated
AC-3 algorithm crucially depends on the commutativity of certain
projection functions.
- Contact Person
-
Gianfranco Rossi
[Page last updated on January 21, 2013, 08:18:53.]
|