The Essence of Constraint Propagation

1998/11/13 by Krzysztof R. Apt, Apt, Krzysztof R.
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #I.1.2 #I.2.2 #cs.AI

paper · pdf · doi:10.48550/arxiv.cs/9811024

To appear in Theoretical Computer Science in the special issue devoted to the 24th ICALP conference (Bologna 1997)

arxiv created 1998/11/13 · arxiv updated 2009/11/30

Abstract

We show that several constraint propagation algorithms (also called (local) consistency, consistency enforcing, Waltz, filtering or narrowing algorithms) are instances of algorithms that deal with chaotic iteration. To this end we propose a simple abstract framework that allows us to classify and compare these algorithms and to establish in a uniform way their basic properties.

Related

• The Rough Guide to Constraint Propagation
• The Role of Commutativity in Constraint Propagation Algorithms
• Constraint Propagation as Information Maximization
• Computing Functional and Relational Box Consistency by Structured Propagation in Atomic Constraint Systems
• Automatic Generation of Constraint Propagation Algorithms for Small Finite Domains