MiniZinc with Strings

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

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.
BibTeX
@inproceedings{amadini2016minizinc,
  author = {Roberto Amadini and Pierre Flener and Justin Pearson and Joseph D. Scott and Peter J. Stuckey and Guido Tack},
  title = {{MiniZinc with Strings}},
  booktitle = {LOPSTR},
  year = {2016},
  doi = {10.1007/978-3-319-63139-4\_4},
}

Loading related content...

Figure