Sweep-based propagation for string constraint solving

Roberto Amadini; Graeme Gange; Peter J. Stuckey

Sweep-based propagation for string constraint solving

Roberto Amadini, Graeme Gange, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

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 language	English
Title of host publication	The Thirty-Second AAAI Conference on Artificial Intelligence
Editors	Sheila McIlraith, Kilian Weinberger
Place of Publication	Palo Alto CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	6557-6564
Number of pages	8
ISBN (Electronic)	9781577358008
Publication status	Published - 2018
Externally published	Yes
Event	AAAI Conference on Artificial Intelligence 2018 - New Orleans, United States of America Duration: 2 Feb 2018 → 7 Feb 2018 Conference number: 32nd https://aaai.org/Conferences/AAAI-18/

Conference

Conference	AAAI Conference on Artificial Intelligence 2018
Abbreviated title	AAAI 2018
Country/Territory	United States of America
City	New Orleans
Period	2/02/18 → 7/02/18
Internet address	https://aaai.org/Conferences/AAAI-18/

Access to Document

271020662-oaFinal published version, 136 KB

https://aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16223

Cite this

@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 = "The Thirty-Second AAAI Conference on Artificial Intelligence",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

address = "United States of America",

note = "AAAI Conference on Artificial Intelligence 2018, AAAI 2018 ; Conference date: 02-02-2018 Through 07-02-2018",

url = "https://aaai.org/Conferences/AAAI-18/",

}

Amadini, R, Gange, G & Stuckey, PJ 2018, Sweep-based propagation for string constraint solving. in S McIlraith & K Weinberger (eds), The Thirty-Second AAAI Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 6557-6564, AAAI Conference on Artificial Intelligence 2018, New Orleans, Louisiana, United States of America, 2/02/18. <https://aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16223>

Sweep-based propagation for string constraint solving. / Amadini, Roberto; Gange, Graeme; Stuckey, Peter J.
The Thirty-Second AAAI Conference on Artificial Intelligence. 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 proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Sweep-based propagation for string constraint solving

AU - Amadini, Roberto

AU - Gange, Graeme

AU - Stuckey, Peter J.

N1 - Conference code: 32nd

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

AN - SCOPUS:85053113318

SP - 6557

EP - 6564

BT - The Thirty-Second AAAI Conference on Artificial Intelligence

A2 - McIlraith, Sheila

A2 - Weinberger, Kilian

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

CY - Palo Alto CA USA

T2 - AAAI Conference on Artificial Intelligence 2018

Y2 - 2 February 2018 through 7 February 2018

ER -

Sweep-based propagation for string constraint solving

Abstract

Conference

Access to Document

Other files and links

Towards reliability in combinatorial optimisation

Cite this

Sweep-based propagation for string constraint solving

Abstract

Conference

Access to Document

Other files and links

Projects

Towards reliability in combinatorial optimisation

Cite this