resented by a DAG where each node represents a range of values for a variable, and a path from the root to a leaf represents a set of satisfying assignments [17].

## 8 Conclusions

We have shown how to transform a GRAMMAR constraint into a REGULAR constraint specified. In the worst case, the transformation may increase the space required to represent the constraint. However, in practice, we observed that such transformation reduces the space required to represent the constraint and speeds up propagation. We argued that transformation also permits us to compress the representation using standard techniques for automaton minimization. We proved that minimizing such automata after they have been unfolded and domains initially reduced can give automata that are exponentially more compact than those obtained by minimizing before unfolding and reducing. Experimental results demonstrated that such transformations can improve the size of rostering problems that can be solved.

## References

1. Pesant, G.: A regular language membership constraint for finite sequences of variables. In CP04, 482–495, 2004 2. Sellmann, M.: The theory of grammar constraints. In CP06, 530–544, 2006 3. Quimper, C.G., Walsh, T.: Global grammar constraints. In CP06, 751–755, 2006 4. Quimper, C.G., Walsh, T.: Decomposing global grammar constraints. In CP07, 590–604, 2007 5. Hopcroft, J. and Ullman, J.: Introduction to Automata Theory, Languages, and Computation.

Addison Wesley Publishing Company, 1979.

6. Darwiche, A.: On the tractable counting of theory models and its application to truth maintenance and belief revision. J. of Applied Non-Classical Logics 11 (2001) 11–34 7. Meyer, A., Stockmeyer, L.: The equivalence problem for regular expressions with squaring requires exponential space. In: 13th Annual Symposium on Switching and Automata Theory, IEEE (1972) 125–129 8. Amilhastre, J., Janssen, P., Vilarem, M.C.: FA minimisation heuristics for a class of finite languages. In WIA99, 1–12, 1999 9. Revuz, D.: Minimization of ayclic deterministic automata in linear time. TCS 92 (1992)
181–189 10. Bacchus, F.: GAC via unit propagation. In CP07, 133–147, 2007 11. Demassey, S., Pesant, G., Rousseau, L.M.: Constraint programming based column generation for employee timetabling. In CPAIOR05, 140–154, 2005 12. Beldiceanu, N., Carlsson, M., Petit, T.: Deriving filtering algorithms from constraint checkers. In CP04, 107–122, 2004 13. Kadioglu, S., Sellmann, M.: Efficient context-free grammar constraints. In AAAI08, 310–
316, 2008 14. Cote, M.C., Bernard, G., Claude-Guy, Q., Louis-Martin, R.: Formal languages for integer programming modeling of shift scheduling problems. TR (2007)
15. Lagerkvist, M.: Techniques for Efficient Constraint Propagation. PhD thesis, KTH, Sweden
(2008). Licentiate thesis.

16. Katsirelos, G., Walsh, T.: A compression algorithm for large arity extensional constraints.

In CP07, 379–393, 2007 17. Carlsson, M.: Filtering for the case constraint (2006). Talk given at Advanced School on Global Constraints, Samos, Greece.