Beldiceanu, Nicolas and Carlsson, Mats and Petit, Thierry (2004) *Deriving filtering algorithms from constraint checkers.* In: Principles and Practice of Constraint Programming – CP 2004, 10th International Conference, 27 Sept - 1 Oct 2004, Toronto, Canada.

Full text not available from this repository.

## Abstract

This article deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n, where n is the number of variables of the corresponding global constraint. By reformulating the automaton as a conjunction of signature and transition constraints we show how to systematically obtain a filtering algorithm. Under some restrictions on the signature and transition constraints this filtering algorithm achieves arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide a filtering algorithm for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.

Item Type: | Conference or Workshop Item (Paper) |
---|---|

Additional Information: | Lecture Notes in Computer Science; 3258, ISBN 978-3-540-23241-4, Extended version available as SICS Tech Report T2004:08 |

ID Code: | 2720 |

Deposited By: | INVALID USER |

Deposited On: | 21 May 2008 |

Last Modified: | 18 Nov 2009 16:13 |

Repository Staff Only: item control page