Dashed strings and the REPLACE(-all) constraint

Roberto Amadini, Graeme Gange, Peter J. Stuckey

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

1 Citation (Scopus)

Abstract

Dashed strings are a formalism for modelling the domain of string variables when solving combinatorial problems with string constraints. In this work we focus on (variants of) the Replace constraint, which aims to find the first occurrence of a query string in a target string, and (possibly) replaces it with a new string. We define a Replace propagator which can also handle Replace-Last (for replacing the last occurrence) and Replace-All (for replacing all the occurrences). Empirical results clearly show that string constraint solving can draw great benefit from this approach.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings
EditorsHelmut Simonis
Place of PublicationCham Switzerland
PublisherSpringer
Pages3-20
Number of pages18
ISBN (Electronic)9783030584757
ISBN (Print)9783030584740
DOIs
Publication statusPublished - 2020
EventInternational Conference on Principles and Practice of Constraint Programming 2020 - Louvain-la-Neuve, Belgium
Duration: 7 Sep 202011 Sep 2020
Conference number: 26th
https://link.springer.com/book/10.1007/978-3-030-58475-7 (Proceedings)
https://cp2020.a4cp.org (Website)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12333
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2020
Abbreviated titleCP2020
CountryBelgium
CityLouvain-la-Neuve
Period7/09/2011/09/20
Internet address

Cite this

Amadini, R., Gange, G., & Stuckey, P. J. (2020). Dashed strings and the REPLACE(-all) constraint. In H. Simonis (Ed.), Principles and Practice of Constraint Programming: 26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings (pp. 3-20). (Lecture Notes in Computer Science ; Vol. 12333). Springer. https://doi.org/10.1007/978-3-030-58475-7_1