Space-time tradeoffs for the regular constraint

Abstract

Many global constraints can be described by a regular expression or a DFA. Originally, the regular constraint, uses a DFA to describe the constraint, however, it can also be used to express a table constraint. Thus, there are many representations for an equivalent constraint. In this paper, we investigate the effect of different representations on natural extensions of the regular constraint focusing on the space-time tradeoffs. We propose a variant of the regular constraint, nfac(X), where X can be an NFA, DFA or MDD. Our nfac algorithm enforces GAC directly on any of the input representations, thus, generalizing the mddc algorithm. We also give an algorithm to directly convert an NFA representation to an MDD for nfac(MDD) or mddc. Our experiments show that the NFA representation not only saves space but also time. When the ratio of the NFA over the MDD or DFA size is small enough, nfac(NFA) is faster. When the size ratio is larger, nfac(NFA) still saves space and is a bit slower. In some problems, the initialization cost of MDD or DFA can also be a significant overhead, unlike NFA which has low initialization cost. We also show that the effect of the early-cutoff optimization is significant in all the representations. © 2012 Springer-Verlag.