SODA

Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators

Beldiceanu, Nicolas and Carlsson, Mats and Flener, Pierre and Rodríguez, María Andreína Francisco and Pearson, Justin (2014) Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators. In: 20th International Conference, CP 2014, 8-12 September 2014, Lyon, France.

Full text not available from this repository.

Official URL: http://link.springer.com/chapter/10.1007/978-3-319...

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.

Item Type:Conference or Workshop Item (Paper)
ID Code:5727
Deposited By:Mats Carlsson
Deposited On:04 Nov 2014 09:03
Last Modified:04 Nov 2014 09:03

Repository Staff Only: item control page