A novel approach to string constraint solving

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

    6 Citations (Scopus)


    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
    Number of pages18
    ISBN (Electronic)9783319661582
    ISBN (Print)9783319661575
    Publication statusPublished - 2017
    EventInternational Conference on Principles and Practice of Constraint Programming 2017 - Melbourne, Australia
    Duration: 28 Aug 20171 Sep 2017
    Conference number: 23rd

    Publication series

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


    ConferenceInternational Conference on Principles and Practice of Constraint Programming 2017
    Abbreviated titleCP 2017
    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