2.4. Describing global constraints in terms of automata

This section is based on the article describing global constraint in terms of automata [BeldiceanuCarlssonPetit04]. The main difference with the original article is the introduction of array of counters within the description of an automaton. We consider global constraints for which any ground instance can be checked in linear time by scanning once through their variables without using any data structure, except counters or arrays of counters. In order to concretely illustrate this point we first select a set of global constraints and write down a checker for each of them. Finally, we give for each checker a sketch of the corresponding automaton. Based on these observations, we define the type of automaton we use in the catalogue.