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

    7 Citations (Scopus)

    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.

    Original 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
    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). Springer. https://doi.org/10.1007/978-3-319-63139-4_4