From Chaotic Iteration to Constraint Propagation

We show how the constraint propagation process can be naturally explained by means of chaotic iteration. 1991 Mathematics Subject Classification: 68Q60, 68N05 1991 Computing Reviews Classification System: F.3.1, I.2.2 Keywords and Phrases: chaotic iterations, constraint propagation algorithms. Note: This paper will appear as an invited lecture in Proceedings of the 24th International Colloquium on Automata, Languages, and Programming (ICALP '97). Work carried out under project PNA1.2, CIP. 1. Introduction 1.1 Motivation Over the last ten years constraint programming emerged as an interesting and viable approach to programming. In this approach the programming process is limited to a generation of requirements ("constraints") and a solution of these requirements by means of general and domain specific methods. The techniques useful for finding solutions to sets of constraints were studied for some twenty years in the field of Constraint Satisfaction. One of the most important of t..