Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators

Nicolas Beldiceanu 1 Mats Carlsson 2 Pierre Flener 3 Maria Andreina 3 Justin Pearson 3
1 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Abstract : Consider a constraint on a sequence of variables functionally determining a result variable that is unchanged under reversal of the sequence. Most such constraints have a compact encoding via an automaton augmented with accumulators, but it is unknown how to maintain domain consistency efficiently for most of them. Using such an automaton for such a constraint, we derive an implied constraint between the result variables for a sequence, a prefix thereof, and the corresponding suffix. We show the usefulness of this implied constraint in constraint solving, both by local search and by propagation-based systematic search.
Type de document :
Communication dans un congrès
Barry O'Sullivan. Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Sep 2014, Lyon, France. Springer, Lecture Notes in Computer Science, 8656, pp.15, 2014, Principles and Practice of Constraint Programming. 〈10.1007/978-3-319-10428-7_13〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01086755
Contributeur : Contraintes Lina <>
Soumis le : lundi 24 novembre 2014 - 17:55:17
Dernière modification le : vendredi 22 juin 2018 - 09:32:21

Identifiants

Citation

Nicolas Beldiceanu, Mats Carlsson, Pierre Flener, Maria Andreina, Justin Pearson. Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators. Barry O'Sullivan. Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Sep 2014, Lyon, France. Springer, Lecture Notes in Computer Science, 8656, pp.15, 2014, Principles and Practice of Constraint Programming. 〈10.1007/978-3-319-10428-7_13〉. 〈hal-01086755〉

Partager

Métriques

Consultations de la notice

325