Sweep-based propagation for string constraint solving

Roberto Amadini, Graeme Gange, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationThe Thirty-Second AAAI Conference on Artificial Intelligence
EditorsSheila McIlraith, Kilian Weinberger
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages6557-6564
Number of pages8
ISBN (Electronic)9781577358008
Publication statusPublished - 2018
Externally publishedYes
EventAAAI Conference on Artificial Intelligence 2018 - New Orleans, United States of America
Duration: 2 Feb 20187 Feb 2018
Conference number: 32nd
https://aaai.org/Conferences/AAAI-18/

Conference

ConferenceAAAI Conference on Artificial Intelligence 2018
Abbreviated titleAAAI 2018
CountryUnited States of America
CityNew Orleans
Period2/02/187/02/18
Internet address

Cite this

Amadini, R., Gange, G., & Stuckey, P. J. (2018). Sweep-based propagation for string constraint solving. In S. McIlraith, & K. Weinberger (Eds.), The Thirty-Second AAAI Conference on Artificial Intelligence (pp. 6557-6564). Association for the Advancement of Artificial Intelligence (AAAI). https://aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16223