  This paper describes a new approach on optimization of constraint
satisfaction problems (CSPs) by means of substituting sub-CSPs with locally
consistent regular membership constraints. The purpose of this approach is to
reduce the number of fails in the resolution process, to improve the inferences
made during search by the constraint solver by strengthening constraint
propagation, and to maintain the level of propagation while reducing the cost
of propagating the constraints. Our experimental results show improvements in
terms of the resolution speed compared to the original CSPs and a
competitiveness to the recent tabulation approach. Besides, our approach can be
realized in a preprocessing step, and therefore wouldn't collide with
redundancy constraints or parallel computing if implemented.
