MiniZinc with strings. (English) Zbl 1485.68027

Hermenegildo, Manuel V. (ed.) et al., Logic-based program synthesis and transformation. 26th international symposium, LOPSTR 2016, Edinburgh, UK, September 6–8, 2016. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10184, 59-75 (2017).
Summary: 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.
For the entire collection see [Zbl 1369.68025].


68N15 Theory of programming languages
68N20 Theory of compilers and interpreters
68W32 Algorithms on strings
Full Text: DOI arXiv Link