Automatic Generation of Constraint Propagation Algorithms for Small Finite Domains

Details Automatic Generation of Constraint Propagation Algorithms for Small Finite Domains Automatic Generation of Constraint Propagation Algorithms for Small Finite Domains

1999-09-08

arxiv.org/abs/cs/9909010v1

Computer Science

Artificial Intelligence

15 pages. To appear in the Proc. 5th International Conference on Principles and Practice of Constraint Programming

Scientific paper

We study here constraint satisfaction problems that are based on predefined, explicitly given finite constraints. To solve them we propose a notion of rule consistency that can be expressed in terms of rules derived from the explicit representation of the initial constraints. This notion of local consistency is weaker than arc consistency for constraints of arbitrary arity but coincides with it when all domains are unary or binary. For Boolean constraints rule consistency coincides with the closure under the well-known propagation rules for Boolean constraints. By generalizing the format of the rules we obtain a characterization of arc consistency in terms of so-called inclusion rules. The advantage of rule consistency and this rule based characterization of the arc consistency is that the algorithms that enforce both notions can be automatically generated, as CHR rules. So these algorithms could be integrated into constraint logic programming systems such as Eclipse. We illustrate the usefulness of this approach to constraint propagation by discussing the implementations of both algorithms and their use on various examples, including Boolean constraints, three valued logic of Kleene, constraints dealing with Waltz's language for describing polyhedreal scenes, and Allen's qualitative approach to temporal logic.

Affiliated with

Also associated with

No associations

Rating

Automatic Generation of Constraint Propagation Algorithms for Small Finite Domains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Automatic Generation of Constraint Propagation Algorithms for Small Finite Domains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic Generation of Constraint Propagation Algorithms for Small Finite Domains will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-89033