Conference Proceedings

Sweep-based propagation for string constraint solving

R Amadini, G Gange, PJ Stuckey

Proceedings of the 2018 AAAI Conference on Artificial Intelligence | Association for the Advancement of Artificial Intelligence | Published : 2018


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.


Awarded by Australian Research Council (ARC)

Funding Acknowledgements

This work is supported by the Australian Research Council (ARC) through Linkage Project Grant LP140100437 and Discovery Early Career Researcher Award DE160100568.