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 publicationProceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 )
Subtitle of host publicationNew Orleans, Louisiana USA — February 2–7, 2018
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.), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 ): New Orleans, Louisiana USA — February 2–7, 2018 (pp. 6557-6564). Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI).
Amadini, Roberto ; Gange, Graeme ; Stuckey, Peter J. / Sweep-based propagation for string constraint solving. Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 ): New Orleans, Louisiana USA — February 2–7, 2018. editor / Sheila McIlraith ; Kilian Weinberger. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2018. pp. 6557-6564
@inproceedings{6aca31493fd24b1e8cd0e8e9c78e6180,
title = "Sweep-based propagation for string constraint solving",
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.",
author = "Roberto Amadini and Graeme Gange and Stuckey, {Peter J.}",
year = "2018",
language = "English",
pages = "6557--6564",
editor = "McIlraith, {Sheila } and Weinberger, {Kilian }",
booktitle = "Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 )",
publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",
address = "United States of America",

}

Amadini, R, Gange, G & Stuckey, PJ 2018, Sweep-based propagation for string constraint solving. in S McIlraith & K Weinberger (eds), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 ): New Orleans, Louisiana USA — February 2–7, 2018. Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 6557-6564, AAAI Conference on Artificial Intelligence 2018, New Orleans, United States of America, 2/02/18.

Sweep-based propagation for string constraint solving. / Amadini, Roberto; Gange, Graeme; Stuckey, Peter J.

Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 ): New Orleans, Louisiana USA — February 2–7, 2018. ed. / Sheila McIlraith; Kilian Weinberger. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2018. p. 6557-6564.

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

TY - GEN

T1 - Sweep-based propagation for string constraint solving

AU - Amadini, Roberto

AU - Gange, Graeme

AU - Stuckey, Peter J.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85053113318&partnerID=8YFLogxK

M3 - Conference Paper

SP - 6557

EP - 6564

BT - Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 )

A2 - McIlraith, Sheila

A2 - Weinberger, Kilian

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Palo Alto CA USA

ER -

Amadini R, Gange G, Stuckey PJ. Sweep-based propagation for string constraint solving. In McIlraith S, Weinberger K, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 ): New Orleans, Louisiana USA — February 2–7, 2018. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2018. p. 6557-6564