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 CP 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 on only integer variables. 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.
Introduction
Strings are the backbone of modern computing, yet they are notoriously difficult to reason about in formal logic. In fields like software analysis, test-case generation, and web security (e.g., detecting SQL injection), researchers need to solve constraints over strings of unknown lengths. While specialized "string solvers" exist, the broader Constraint Programming (CP) community has largely lacked a unified way to model these problems. Most CP solvers are designed for integers and real numbers. Before this work, using a powerful CP solver like Gecode or Chuffed on a string problem required manually translating every string operation into complex integer arrays—a tedious and error-prone process.
Language Extensions and Modeling
The authors propose a two-pronged extension to the MiniZinc ecosystem. First, they introduced var string as a first-class citizen in MiniZinc. This includes a library of standard functions: concatenation (++), length (str_len), sub-string selection, and even complex constraints like Regular Expression (DFA/NFA) membership and Global Cardinality (counting character occurrences).
The $\mathcal{F}^{int}$ Transformation
The second part of the extension is the "magic" under the hood: the $\mathcal{F}^{int}$ transformation. For solvers that do not support strings natively, MiniZinc now includes a library that automatically "flattens" string variables into arrays of integers (representing ASCII codes).
- Padding & Length: Since MiniZinc arrays usually have fixed sizes, the authors use an "open-sequence" representation. A string is mapped to an array of length $L$ (the maximum possible length), an integer variable for the actual length, and "trailing zeros" to pad the unused space.
- Automata Tweaking: To handle regular expression constraints (DFAs) on these padded arrays, they developed a method to modify the automaton so it correctly ignores the padding characters.
Experimental Evaluation
The framework was evaluated using the Norn Benchmark (a set of five challenging problems: anb_n, ChunkSplit, HammingDistance, Levenshtein, and StringReplace) and a custom Palindrome Problem designed to find the minimum-length palindrome with specific character counts.
Key Results and Insights
- Native vs. Decomposed: Gecode+S (which has native string support) was generally the fastest and most robust across the board. However, on certain benchmarks like the Palindrome problem, solvers using the $\mathcal{F}^{int}$ decomposition (like Chuffed and iZplus) actually outperformed native solvers in search speed.
- The Flattening Bottleneck: A significant finding is that the bottleneck isn't always the solving time, but the compilation time. Turning a single string constraint into thousands of integer constraints for a long string can result in massive FlatZinc files (e.g., jumping from 14 lines to 45,000 lines).
- Scalability: The framework successfully handled string lengths up to 1,000 characters, though performance degrades as the maximum bound increases due to the quadratic growth of some decomposed constraints.
Conclusion and Future Work
This work proves that "Model Once, Solve Anywhere" is now a reality for strings in MiniZinc. While currently limited to the ASCII character set and requiring a fixed maximum length ($L$), the framework allows general-purpose solvers to leverage advanced search heuristics like "lazy clause generation" for string problems. Future work will focus on extending support to Unicode and developing "string-aware" search heuristics to further improve efficiency.
Summary updated