Skip to Main content Skip to Navigation
New interface
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Contraintes Lina Connect in order to contact the contributor
Submitted on : Monday, November 24, 2014 - 5:55:17 PM
Last modification on : Wednesday, April 27, 2022 - 3:42:54 AM



Nicolas Beldiceanu, Mats Carlsson, Pierre Flener, Maria Andreina, Justin Pearson. Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators. Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Sep 2014, Lyon, France. pp.15, ⟨10.1007/978-3-319-10428-7_13⟩. ⟨hal-01086755⟩



Record views