A novel approach to string constraint solving

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

    5 Citations (Scopus)

    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.

    Original 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/

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