  When eating spaghetti, one should have the sauce and noodles mixed instead of
eating them separately. We argue that also in string solving, word equations
and regular constraints are better mixed together than approached separately as
in most current string solvers. We propose a fast algorithm, complete for the
fragment of chain-free constraints, in which word equations and regular
constraints are tightly integrated and exchange information, efficiently
pruning the cases generated by each other and limiting possible combinatorial
explosion. The algorithm is based on a novel language-based characterisation of
satisfiability of word equations with regular constraints. We experimentally
show that our prototype implementation is competitive with the best string
solvers and even superior in that it is the fastest on difficult examples and
has the least number of timeouts.
