Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators

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.

Carlsson, MatsRISE,Computer Systems Laboratory(Swepub:ri)MatsCa@ri.se (författare)
Flener, PierreUppsala universitet,Datalogi,ASTRA,Uppsala University, Sweden(Swepub:uu)pfl08519 (författare)
Francisco Rodríguez, María AndreínaUppsala universitet,Datalogi,ASTRA,Uppsala University, Sweden(Swepub:uu)marfr379 (författare)
Pearson, JustinUppsala universitet,Datalogi,ASTRA,Uppsala University, Sweden(Swepub:uu)justpear (författare)
CNRS INRIA, FranceComputer Systems Laboratory (creator_code:org_t)

Ingår i:Principles and Practice of Constraint ProgrammingCham : Springer International Publishing, s. 142-1579783319104270

Av författaren/redakt...: Beldiceanu, Nico ...; Carlsson, Mats; Flener, Pierre; Francisco Rodríg ...; Pearson, Justin

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.