MiniZinc with strings

Roberto Amadini, Pierre Flener, Justin Pearson, Joseph D. Scott, Peter J. Stuckey, Guido Tack

    Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review

    Abstract

    Strings are extensively used in modern programming languages and constraints over strings of unknown length occur in a wide range of real-world applications such as software analysis and verification, testing, model checking, and web security. Nevertheless, practically no constraint programming solver natively supports string constraints. We introduce string variables and a suitable set of string constraints as builtin features of the MiniZinc modelling language. Furthermore, we define an interpreter for converting a MiniZinc model with strings into a FlatZinc instance relying only on integer variables. This conversion is obtained via rewrite rules, and does not require any extension of the existing FlatZinc specification. This provides a user-friendly interface for modelling combinatorial problems with strings, and enables both string and non-string solvers to actually solve such problems.

    LanguageEnglish
    Title of host publicationLogic-Based Program Synthesis and Transformation
    Subtitle of host publication26th International Symposium, LOPSTR 2016, Edinburgh, UK, September 6–8, 2016,Revised Selected Papers
    EditorsManuel V. Hermenegildo, Pedro Lopez-Garcia
    Place of PublicationCham, Switzerland
    PublisherSpringer-Verlag London Ltd.
    Pages59-75
    Number of pages17
    ISBN (Electronic)9783319631394
    ISBN (Print)9783319631387
    DOIs
    Publication statusPublished - 2017
    EventInternational Symposium on Logic-Based Program Synthesis and Transformation 2016 - Edinburgh, United Kingdom
    Duration: 6 Sep 20168 Sep 2016

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    PublisherSpringer
    Volume10184 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    ConferenceInternational Symposium on Logic-Based Program Synthesis and Transformation 2016
    CountryUnited Kingdom
    CityEdinburgh
    Period6/09/168/09/16

    Cite this

    Amadini, R., Flener, P., Pearson, J., Scott, J. D., Stuckey, P. J., & Tack, G. (2017). MiniZinc with strings. In M. V. Hermenegildo, & P. Lopez-Garcia (Eds.), Logic-Based Program Synthesis and Transformation : 26th International Symposium, LOPSTR 2016, Edinburgh, UK, September 6–8, 2016,Revised Selected Papers (pp. 59-75). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10184 LNCS). Cham, Switzerland: Springer-Verlag London Ltd.. https://doi.org/10.1007/978-3-319-63139-4_4
    Amadini, Roberto ; Flener, Pierre ; Pearson, Justin ; Scott, Joseph D. ; Stuckey, Peter J. ; Tack, Guido. / MiniZinc with strings. Logic-Based Program Synthesis and Transformation : 26th International Symposium, LOPSTR 2016, Edinburgh, UK, September 6–8, 2016,Revised Selected Papers. editor / Manuel V. Hermenegildo ; Pedro Lopez-Garcia. Cham, Switzerland : Springer-Verlag London Ltd., 2017. pp. 59-75 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
    @inbook{ba8f5f6e145641f6997957be91e6e7e7,
    title = "MiniZinc with strings",
    abstract = "Strings are extensively used in modern programming languages and constraints over strings of unknown length occur in a wide range of real-world applications such as software analysis and verification, testing, model checking, and web security. Nevertheless, practically no constraint programming solver natively supports string constraints. We introduce string variables and a suitable set of string constraints as builtin features of the MiniZinc modelling language. Furthermore, we define an interpreter for converting a MiniZinc model with strings into a FlatZinc instance relying only on integer variables. This conversion is obtained via rewrite rules, and does not require any extension of the existing FlatZinc specification. This provides a user-friendly interface for modelling combinatorial problems with strings, and enables both string and non-string solvers to actually solve such problems.",
    author = "Roberto Amadini and Pierre Flener and Justin Pearson and Scott, {Joseph D.} and Stuckey, {Peter J.} and Guido Tack",
    year = "2017",
    doi = "10.1007/978-3-319-63139-4_4",
    language = "English",
    isbn = "9783319631387",
    series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
    publisher = "Springer-Verlag London Ltd.",
    pages = "59--75",
    editor = "Hermenegildo, {Manuel V. } and Lopez-Garcia, {Pedro }",
    booktitle = "Logic-Based Program Synthesis and Transformation",
    address = "Germany",

    }

    Amadini, R, Flener, P, Pearson, J, Scott, JD, Stuckey, PJ & Tack, G 2017, MiniZinc with strings. in MV Hermenegildo & P Lopez-Garcia (eds), Logic-Based Program Synthesis and Transformation : 26th International Symposium, LOPSTR 2016, Edinburgh, UK, September 6–8, 2016,Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10184 LNCS, Springer-Verlag London Ltd., Cham, Switzerland, pp. 59-75, International Symposium on Logic-Based Program Synthesis and Transformation 2016, Edinburgh, United Kingdom, 6/09/16. https://doi.org/10.1007/978-3-319-63139-4_4

    MiniZinc with strings. / Amadini, Roberto; Flener, Pierre; Pearson, Justin; Scott, Joseph D.; Stuckey, Peter J.; Tack, Guido.

    Logic-Based Program Synthesis and Transformation : 26th International Symposium, LOPSTR 2016, Edinburgh, UK, September 6–8, 2016,Revised Selected Papers. ed. / Manuel V. Hermenegildo; Pedro Lopez-Garcia. Cham, Switzerland : Springer-Verlag London Ltd., 2017. p. 59-75 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10184 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review

    TY - CHAP

    T1 - MiniZinc with strings

    AU - Amadini, Roberto

    AU - Flener, Pierre

    AU - Pearson, Justin

    AU - Scott, Joseph D.

    AU - Stuckey, Peter J.

    AU - Tack, Guido

    PY - 2017

    Y1 - 2017

    N2 - Strings are extensively used in modern programming languages and constraints over strings of unknown length occur in a wide range of real-world applications such as software analysis and verification, testing, model checking, and web security. Nevertheless, practically no constraint programming solver natively supports string constraints. We introduce string variables and a suitable set of string constraints as builtin features of the MiniZinc modelling language. Furthermore, we define an interpreter for converting a MiniZinc model with strings into a FlatZinc instance relying only on integer variables. This conversion is obtained via rewrite rules, and does not require any extension of the existing FlatZinc specification. This provides a user-friendly interface for modelling combinatorial problems with strings, and enables both string and non-string solvers to actually solve such problems.

    AB - Strings are extensively used in modern programming languages and constraints over strings of unknown length occur in a wide range of real-world applications such as software analysis and verification, testing, model checking, and web security. Nevertheless, practically no constraint programming solver natively supports string constraints. We introduce string variables and a suitable set of string constraints as builtin features of the MiniZinc modelling language. Furthermore, we define an interpreter for converting a MiniZinc model with strings into a FlatZinc instance relying only on integer variables. This conversion is obtained via rewrite rules, and does not require any extension of the existing FlatZinc specification. This provides a user-friendly interface for modelling combinatorial problems with strings, and enables both string and non-string solvers to actually solve such problems.

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

    U2 - 10.1007/978-3-319-63139-4_4

    DO - 10.1007/978-3-319-63139-4_4

    M3 - Chapter (Book)

    SN - 9783319631387

    T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

    SP - 59

    EP - 75

    BT - Logic-Based Program Synthesis and Transformation

    A2 - Hermenegildo, Manuel V.

    A2 - Lopez-Garcia, Pedro

    PB - Springer-Verlag London Ltd.

    CY - Cham, Switzerland

    ER -

    Amadini R, Flener P, Pearson J, Scott JD, Stuckey PJ, Tack G. MiniZinc with strings. In Hermenegildo MV, Lopez-Garcia P, editors, Logic-Based Program Synthesis and Transformation : 26th International Symposium, LOPSTR 2016, Edinburgh, UK, September 6–8, 2016,Revised Selected Papers. Cham, Switzerland: Springer-Verlag London Ltd. 2017. p. 59-75. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-63139-4_4