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 metadatas

https://hal.inria.fr/hal-01086755
Contributor : Contraintes Lina <>
Submitted on : Monday, November 24, 2014 - 5:55:17 PM
Last modification on : Friday, June 22, 2018 - 9:32:21 AM

Links full text

Identifiers

Citation

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⟩

Share

Metrics

Record views

359