View article

A wide range of constraints can be specified using automata or formal languages. The Grammar constraint restricts the values taken by a sequence of variables to be a string from a given context-free language. Based on an AND/OR decomposition, we show that this constraint can be converted into clauses in conjunctive normal form without hindering propagation. Using this decomposition, we can propagate the Grammar constraint in O(n ³) time. The decomposition also provides an efficient incremental propagator. Down a branch of the search tree of length k, we can enforce GAC k times in the same O(n ³) time. On specialized languages, running time can be even better. For example, propagation of the decomposition requires just O(n|δ|) time for regular languages where |δ| is the size of the transition table of the automaton recognizing the regular language. Experiments on a shift …