A novel approach to string constraint solving

Roberto Amadini, Graeme Gange, Peter J. Stuckey, Guido Tack

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

Abstract

String processing is ubiquitous across computer science, and arguably more so in web programming. In order to reason about programs manipulating strings we need to solve constraints over strings. In Constraint Programming, the only approaches we are aware for representing string variables—having bounded yet possibly unknown size—degrade when the maximum possible string length becomes too large. In this paper, we introduce a novel approach that decouples the size of the string representation from its maximum length. The domain of a string variable is dynamically represented by a simplified regular expression that we called a dashed string, and the constraint solving relies on propagation of information based on equations between dashed strings. We implemented this approach in G-Strings, a new string solver—built on top of Gecode solver—that already shows some promising results.

LanguageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings
EditorsChristopher Beck
Place of PublicationCham Switzerland
PublisherSpringer
Pages3-20
Number of pages18
Volume10416
ISBN (Electronic)9783319661582
ISBN (Print)9783319661575
DOIs
StatePublished - 2017
EventInternational Conference on Principles and Practice of Constraint Programming 2017 - Melbourne, Australia
Duration: 28 Aug 20171 Sep 2017
Conference number: 23rd
http://cp2017.a4cp.org/
https://link.springer.com/book/10.1007/978-3-319-66158-2 (Conference Proceedings)

Publication series

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

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2017
Abbreviated titleCP 2017
CountryAustralia
CityMelbourne
Period28/08/171/09/17
OtherThe International Conference on Principles and Practice of Constraint Programming will take place in Melbourne, Australia alongside SAT 2017 and ICLP 2017 from August 28th to September 1st, 2017 which is the week immediately following IJCAI 2017.
Internet address

Cite this

Amadini, R., Gange, G., Stuckey, P. J., & Tack, G. (2017). A novel approach to string constraint solving. In C. Beck (Ed.), Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings (Vol. 10416 , pp. 3-20). (Lecture Notes in Computer Science; Vol. 10416). Cham Switzerland: Springer. DOI: 10.1007/978-3-319-66158-2_1
Amadini, Roberto ; Gange, Graeme ; Stuckey, Peter J. ; Tack, Guido. / A novel approach to string constraint solving. Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings. editor / Christopher Beck. Vol. 10416 Cham Switzerland : Springer, 2017. pp. 3-20 (Lecture Notes in Computer Science).
@inproceedings{1fa58c22f1394bfb84863ccd404b72e7,
title = "A novel approach to string constraint solving",
abstract = "String processing is ubiquitous across computer science, and arguably more so in web programming. In order to reason about programs manipulating strings we need to solve constraints over strings. In Constraint Programming, the only approaches we are aware for representing string variables—having bounded yet possibly unknown size—degrade when the maximum possible string length becomes too large. In this paper, we introduce a novel approach that decouples the size of the string representation from its maximum length. The domain of a string variable is dynamically represented by a simplified regular expression that we called a dashed string, and the constraint solving relies on propagation of information based on equations between dashed strings. We implemented this approach in G-Strings, a new string solver—built on top of Gecode solver—that already shows some promising results.",
author = "Roberto Amadini and Graeme Gange and Stuckey, {Peter J.} and Guido Tack",
year = "2017",
doi = "10.1007/978-3-319-66158-2_1",
language = "English",
isbn = "9783319661575",
volume = "10416",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "3--20",
editor = "Beck, {Christopher }",
booktitle = "Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings",

}

Amadini, R, Gange, G, Stuckey, PJ & Tack, G 2017, A novel approach to string constraint solving. in C Beck (ed.), Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings. vol. 10416 , Lecture Notes in Computer Science, vol. 10416, Springer, Cham Switzerland, pp. 3-20, International Conference on Principles and Practice of Constraint Programming 2017, Melbourne, Australia, 28/08/17. DOI: 10.1007/978-3-319-66158-2_1

A novel approach to string constraint solving. / Amadini, Roberto; Gange, Graeme; Stuckey, Peter J.; Tack, Guido.

Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings. ed. / Christopher Beck. Vol. 10416 Cham Switzerland : Springer, 2017. p. 3-20 (Lecture Notes in Computer Science; Vol. 10416).

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

TY - GEN

T1 - A novel approach to string constraint solving

AU - Amadini,Roberto

AU - Gange,Graeme

AU - Stuckey,Peter J.

AU - Tack,Guido

PY - 2017

Y1 - 2017

N2 - String processing is ubiquitous across computer science, and arguably more so in web programming. In order to reason about programs manipulating strings we need to solve constraints over strings. In Constraint Programming, the only approaches we are aware for representing string variables—having bounded yet possibly unknown size—degrade when the maximum possible string length becomes too large. In this paper, we introduce a novel approach that decouples the size of the string representation from its maximum length. The domain of a string variable is dynamically represented by a simplified regular expression that we called a dashed string, and the constraint solving relies on propagation of information based on equations between dashed strings. We implemented this approach in G-Strings, a new string solver—built on top of Gecode solver—that already shows some promising results.

AB - String processing is ubiquitous across computer science, and arguably more so in web programming. In order to reason about programs manipulating strings we need to solve constraints over strings. In Constraint Programming, the only approaches we are aware for representing string variables—having bounded yet possibly unknown size—degrade when the maximum possible string length becomes too large. In this paper, we introduce a novel approach that decouples the size of the string representation from its maximum length. The domain of a string variable is dynamically represented by a simplified regular expression that we called a dashed string, and the constraint solving relies on propagation of information based on equations between dashed strings. We implemented this approach in G-Strings, a new string solver—built on top of Gecode solver—that already shows some promising results.

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

U2 - 10.1007/978-3-319-66158-2_1

DO - 10.1007/978-3-319-66158-2_1

M3 - Conference Paper

SN - 9783319661575

VL - 10416

T3 - Lecture Notes in Computer Science

SP - 3

EP - 20

BT - Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings

PB - Springer

CY - Cham Switzerland

ER -

Amadini R, Gange G, Stuckey PJ, Tack G. A novel approach to string constraint solving. In Beck C, editor, Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings. Vol. 10416 . Cham Switzerland: Springer. 2017. p. 3-20. (Lecture Notes in Computer Science). Available from, DOI: 10.1007/978-3-319-66158-2_1