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
    Publication statusPublished - 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. https://doi.org/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. https://doi.org/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

    A2 - Beck, Christopher

    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). https://doi.org/10.1007/978-3-319-66158-2_1