Skip to Main content Skip to Navigation
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
Inria Rennes – Bretagne Atlantique , Département informatique - EMN, LINA - Laboratoire d'Informatique de Nantes 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 metadatas
Contributor : Contraintes Lina <>
Submitted on : Monday, November 24, 2014 - 5:55:17 PM
Last modification on : Friday, July 10, 2020 - 8:10:04 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