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.]