On Modelling the Avoidability of Patterns as CSP
This provides a unified approach for researchers in string combinatorics to solve avoidability problems more efficiently, though it is incremental as it formalizes existing tasks rather than introducing a new paradigm.
The authors tackled the computationally hard task of solving avoidability problems in string combinatorics by modeling them uniformly as constraint satisfaction problems (CSPs) using MiniZinc, eliminating the need for ad-hoc methods and allowing standard CSP-solvers to handle the search.
Solving avoidability problems in the area of string combinatorics often requires, in an initial step, the construction, via a computer program, of a very long word that does not contain any word that matches a given pattern. It is well known that this is a computationally hard task. Despite being rather straightforward that, ultimately, all such tasks can be formalized as constraints satisfaction problems, no unified approach to solving them was proposed so far, and very diverse ad-hoc methods were used. We aim to fill this gap: we show how several relevant avoidability problems can be modelled, and consequently solved, in an uniform way as constraint satisfaction problems, using the framework of MiniZinc. The main advantage of this approach is that one is now required only to formulate the avoidability problem in the MiniZinc language, and then the actual search for a solution does not have to be implemented ad-hoc, being instead carried out by a standard CSP-solver.