Sweep-based propagation for string constraint solving
R Amadini, G Gange, PJ Stuckey
32nd AAAI Conference on Artificial Intelligence, AAAI 2018 | Association for the Advancement of Artificial Intelligence | Published : 2018
Copyright © 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Solving constraints over strings is an emerging important field. Recently, a Constraint Programming approach based on dashed strings has been proposed to enable a compact domain representation for potentially large bounded-length string variables. In this paper, we present a more efficient algorithm for propagating equality (and related constraints) over dashed strings. We call this propagation sweep-based. Experimental evidences show that sweep-based propagation is able to significantly outperform state-of-the-art approaches for string constraint solving.
Related Projects (1)
Awarded by Australian Research Council (ARC)
This work is supported by the Australian Research Council (ARC) through Linkage Project Grant LP140100437 and Discovery Early Career Researcher Award DE160100568.