A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints

1 Introduction

Many constraints are such that a counting variable is equal to the number of times a given property is satisfied in a sequence of variables. To represent some of these constraints in a generic way, we introduce the SEQ BIN(N,X,C,B) metaconstraint, where N is an integer variable, X is a sequence of integer variables and C and B are two binary constraints.

Based on the notion C-stretch, a generalization of stretch [Pesant, 2001] where the equality constraint is made explicit and is replaced by C, SEQ BIN holds if and only if two conditions are both satisfied: (1) N is equal to the number of C-stretches in the sequence X, and (2) B holds on any pair of consecutive variables in X.

Among the constraints that can be expressed thanks to SEQ BIN, many were introduced for solving real-world problems, e.g., CHANGE [Cosytec, 1997] (time tabling problems), SMOOTH [Beldiceanu et al., 2010a] (time tabling and scheduling), or INCREASING NVALUE [Beldiceanu et al., 2010b] (symmetry breaking for resource allocation problems).

The main contribution of this paper is a generic polytime filtering algorithm for SEQ BIN, achieving generalized arc-consistency (GAC) when the constraint B is monotonic [Van Hentenryck et al., 1992]. This algorithm can be seen as a generalization of the INCREASING NVALUE filtering algorithm [Beldiceanu et al., 2010b]. Given n the size of X, d the maximum domain size, and ΣDi the sum of domain sizes, we characterize properties on C and B which lead to a time and space complexity in O(ΣDi). These properties are satisfied when SEQ BIN represents CHANGE, SMOOTH and INCREASING NVALUE. For all these constraints, our technique improves or equals the best known results.

Section 2 provides the definitions used in this paper. Section 3 defines SEQ BIN and shows how to express well-known constraints with SEQ BIN. Section 4 provides a necessary and sufficient condition for achieving GAC. Section 5 details the corresponding GAC filtering algorithm. Finally, Section 6 discusses about related works and Section 7 concludes.

2 Background

A Constraint Network is defined by a sequence of variables X = [x0, x1, . . . , xn-1], a sequence of domains D, where each D(xi) ∈ D is the finite set of values that variable xi can take, and a set of constraints C that specifies the allowed combinations of values for given subsets of variables. min(x) (resp. max(x)) is the minimum (resp. maximum) value of D(x). A sequence of variables X′ = [xi, xi+1, . . . , xj], 0 ≤ i ≤ j ≤ n-1 (resp. i > 0 or i < n-1), is a subsequence (resp. a strict subsequence) of X and is denoted by X′ ⊆ X (resp. X′ ⊂ X). A[X] denotes an assignment of values to variables in X. Given x ∈ X, A[x] is the value of x in A[X]. A[X] is valid if and only if ∀xi ∈ X, A[xi] ∈ D(xi). An instantiation I[X] is a valid assignment of X. Given x ∈ X, I[x] is the value of x in I[X]. Given the sequence X and i, j two integers such that 0 ≤ i ≤ j ≤ n - 1, I[xi, . . . , xj] is the projection of I[X] on [xi, xi+1, , . . . , xj]. A constraint C(X) ∈ C specifies the allowed combinations of values for X. We also use the simple notation C. C(X) defines a subset RC(D) of the cartesian product of the domains Πxi∈XD(xi). If X is a pair of variables, then C(X) is binary. We denote by vCw a pair of values (v,w) that satisfies a binary constraint C. ¬C is the opposite of C, that is, ¬C defines the relation R¬C(D) = Πxi∈XD(xi) \ RC(D). A feasible instantiation I[X] of C[X] is an instantiation which is in RC(D). We say that I[X] satisfies C(X), or that I[X] is a support on C(X). Otherwise, I[X] violates C(X). If C is a binary constraint on X = {xi, xi+1} and v ∈ D(xi) then the set of supports such that xi = v can be considered as a set of values (a subset of D(xi+1)). A solution of a constraint network is an instantiation of all the variables satisfying all the constraints.

Value v ∈ D(xi), xi ∈ X, is (generalized) arc-consistent (GAC) with respect to C(X) if and only if v belongs to a support of C(X). A domain D(xi), xi ∈ X, is GAC with respect to C(X) if and only if ∀v ∈ D(xi), v is GAC with respect to C(X). C(X) is GAC if and only if ∀xi ∈ X, D(xi) is GAC with respect to C(X). A constraint network is GAC if and only if it is closed for GAC [Bessi`ere, 2006]: ∀xi ∈ X all values in D(xi) that are not GAC with respect

3 The SEQ BIN Meta-Constraint

We first generalize the notion of stretches [Pesant, 2001] to characterize a sequence of consecutive variables where the same binary constraint is satisfied.

Definition 1 (C-stretch). Let I[X] be an instantiation of the variable sequence X = [x0, x1, . . . , xn-1] and C a binary constraint. The C-sequence constraint C(I[X],C) holds if and only if:

• Either n = 1,
• or n > 1 and ∀k ∈ [0, n - 2] C(I[xk], I[xk+1]) holds.

A C-stretch of I[X] is a subsequence X′ ⊆ X such that the two following conditions are both satisfied:

1. The C-sequence C(I[X′ ],C) holds,

The intuition behind Definition 1 is to consider the maximum length subsequences where the binary constraint C is satisfied between consecutive variables. Thanks to this generalized definition of stretches we can now introduce SEQ BIN.

Definition 2. The meta-constraint SEQ BIN(N,X,C,B) is defined by a variable N, a sequence of n variables X = [x0, x1, . . . , xn-1] and two binary constraints C and B. Given an instantiation I[N, x0, x1, . . . , xn-1], SEQ BIN(N,X,C,B) is satisfied if and only if for any i ∈ [0, n - 2], I[xi]B I[xi+1] holds, and I[N] is equal to the number of C-stretches in I[X].

The constraint CHANGE was introduced in the context of timetabling problems [Cosytec, 1997], in order to put an upper limit on the number of changes of job types during a given period. The relation between classical stretches and CHANGE was initially stressed in [Hellsten, 2004, page 64]. CHANGE is defined on a variable N, a sequence of variables X = [x0, x1, . . . , xn-1], and a binary constraint C ∈ {=, ̸= ,<,>,≤,≥}. It is satisfied if and only if N is equal to the number of times the constraint C holds on consecutive variables of X. Without hindering propagation (the constraint network is Berge-acyclic), CHANGE can be reformulated as SEQ BIN(N ′ , X, ¬C,true) ∧ [N = N ′ - 1], where true is the universal constraint.

SMOOTH(N,X) is a variant of CHANGE(N,X,C), where xi C xi+1 is defined by |xi -xi+1| > cst , cst ∈ N. It is useful to limit the number of drastic variations on a cumulative profile [Beldiceanu et al., 2010a; De Clercq, 2010].

As a last example, consider the INCREASING NVALUE constraint, which is a specialized version of NVALUE [Pachet and Roy, 1999]. It was introduced for breaking variable symmetry in the context of resource allocation problems [Beldiceanu et al., 2010b]. INCREASING NVALUE is defined on a variable N and on a sequence of variables X = [x0, x1, . . . , xn-1]. Given an instantiation, INCREASING NVALUE(N,X) is satisfied if and only if N is equal to the number of distinct values assigned to variables in X, and for any i ∈ [0, n - 2], xi ≤ xi+1. We reformulate INCREASING NVALUE(N,X) as SEQ BIN(N,X,=,≤).

4 Consistency of SEQ BIN

We first present how to compute, for any value in a given domain of a variable xi ∈ X, the minimum and maximum number of C-stretches within the suffix of X starting at xi (resp. the prefix of X ending at xi) satisfying a chain of binary constraints of type B. Then, we introduce several properties useful to obtain a feasibility condition for SEQ BIN, and a necessary and sufficient condition for filtering which leads to the GAC filtering algorithm presented in Section 5.

4.1 Computing of the Number of C-stretches

According to Definition 2, we have to ensure that the chain of B constraints are satisfied along the sequence of variables X = [x0, x1, . . . , xn-1]. An instantiation I[X] is said B-coherent if and only if either n = 1 or for any i ∈ [0, n-2], we have I[xi]B I[xi+1]. A value v ∈ D(xi) is said to be B-coherent with respect to xi if and only if it can be part of at least one B-coherent instantiation. Then, given an integer i ∈ [0, n - 2], if v ∈ D(xi) is B-coherent with respect to xi then there exists w ∈ D(xi+1) such that v B w.

Consequently, within a given domain D(xi), values that are not B-coherent can be removed since they cannot be part of any solution of SEQ BIN. Our aim is now to compute for each B-coherent value v in the domain of any variable xi the minimum and maximum number of C-stretches on X.

Notation 1. s(xi, v) (resp. s(xi, v)) is the minimum (resp. maximum) number of C-stretches within the sequence of variables [xi, xi+1, . . . , xn-1] under the hypothesis that xi = v. p(xi, v) (resp. p(xi, v)) is the minimum (resp. maximum) number of C-stretches within the sequence [x0, x1, . . . , xi] under the hypothesis that xi = v. Given X = [x0, x1, . . . , xn-1], s(X) (resp. s(X)) denotes the minimum (resp. maximum) value of s(x0, v) (resp. s(x0, v)).

Lemma 1. Given SEQ BIN(N,X,C,B) with X = [x0, x1, . . . , xn-1], assume the domains in X contain only B-coherent values. Given i ∈ [0, n - 1] and v ∈ D(xi),

• If i = n-1: s(xn-1, v) = 1.
• Else:

Proof. By induction. From Definition 1, for any v ∈ D(xn-1), we have s(xn-1, v) = 1 (i.e., a C-stretch of length 1). Consider now xi ∈ X with i < n - 1, and a value v ∈ D(xi). Consider the set of instantiations I[xi+1, xi+2, . . . , xn-1] that are B-coherent, and that minimize the number of C-stretches in [xi+1, xi+2, . . . , xn-1]. We denote this minimum number of C-stretches by mins . At least one B-coherent instantiation exists since all values in the domains of [xi+1, xi+2, . . . , xn-1] are B-coherent. For each such instantiation, let us denote by w the value associated with I[xi+1]. Either there exists such an instantiation with mins C-stretches with the conjunction B ∧ C satisfied by (I[xi], I[xi+1]). Then, s(xi, v) = s(xi+1,w) since the first C-stretch of I[xi+1, xi+2, . . . , xn-1] is extended when augmenting I[xi+1, xi+2, . . . , xn-1] with value v for xi. Or all instantiations I[xi+1, xi+2, . . . , xn-1] with mins C-stretches are such that C is violated by (I[xi], I[xi+1]): (I[xi], I[xi+1]) satisfies B∧¬C. By construction, any instantiation I[xi, xi+1, . . . , xn-1] with I[xi] = v has a number of C-stretches strictly greater than mins. Consequently, given I[xi+1, xi+2, . . . , xn-1] with mins C-stretches, the number of C-stretches obtained by augmenting this instantiation with value v for xi is exactly mins + 1.

Lemma 2. Given SEQ BIN(N,X,C,B) with X = [x0, x1, . . . , xn-1], assume the domains in X contain only B-coherent values. Given i ∈ [0, n - 1] and v ∈ D(xi):

• If i = n-1: s(xn-1, v) = 1.
• Else:

Given a sequence of variables [x0, x1, . . . , xn-1] such that their domains contain only B-coherent values, for any xi in the sequence and any v ∈ D(xi), computing p(xi, v) (resp. p(xi, v)) is symmetrical to s(xi, v) (resp. s(xi, v)). We substitute min by max (resp. max by min), xi+1 by xi-1, and vRw by wRv for any R ∈ {B, C, ¬C}.

4.2 Properties on the Number of C-stretches

This section provides the properties linking the values in a domain D(xi) with the minimum and maximum number of C-stretches in X. We consider only B-coherent values, which may be part of a feasible instantiation of SEQ BIN. Next property is a direct consequence of Lemmas 1 and 2.

Property 1. For any B-coherent value v in D(xi), with respect to xi, s(xi, v) ≤ s(xi, v).

Property 2. Consider SEQ BIN(N,X,C,B), a variable xi ∈ X (0 ≤ i ≤ n - 1), and two B-coherent values v1, v2 ∈ D(xi). If i = n - 1 or if there exists a B-coherent w ∈ D(xi+1) such that v1Bw and v2Bw, then s(xi, v1) + 1 ≥ s(xi, v2).

Proof. Obviously, if i = n - 1. If v1 = v2, by Property 1 the property holds. Otherwise, assume there exist two values v1 and v2 such that ∃w ∈ D(xi+1) for which v1Bw and v2Bw, and s(xi, v1) + 1 < s(xi, v2) (hypothesis H). By Lemma 2, s(xi, v1) ≥ s(xi+1, w). By Lemma 1, s(xi, v2) ≤ s(xi+1, w)+1. From hypothesis H, this entails s(xi+1, w)+ 1 < s(xi+1, w)+1, which leads to s(xi+1, w) < s(xi+1, w), which is, by Property 1, not possible.

Property 3. Consider SEQ BIN(N,X,C,B), a variable xi ∈ X (0 ≤ i ≤ n - 1), and two B-coherent values v1, v2 ∈ D(xi). If either i = n - 1 or there exists B-coherent w ∈ D(xi+1) such that v1 Bw and v2 Bw then, for any k ∈ [min(s(xi, v1), s(xi, v2)), max(s(xi, v1), s(xi, v2))], either k ∈ [s(xi, v1), s(xi, v1)] or k ∈ [s(xi, v2), s(xi, v2)].

Proof. Obviously, if i = n - 1 or v1 = v2 . If [s(xi, v1), s(xi, v1)] ∩ [s(xi, v2), s(xi, v2)] is not empty, then the property holds. Assume [s(xi, v1), s(xi, v1)] and [s(xi, v2), s(xi, v2)] are disjoint. W.l.o.g., assume s(xi, v1) < s(xi, v2). By Property 2, s(xi, v1) + 1 ≥ s(xi, v2), thus s(xi, v1) = s(xi, v2) - 1. Either k ∈

[s(xi, v1), s(xi, v1)] or k ∈ [s(xi, v2), s(xi, v2)] (there is no hole in the range formed by the union of these intervals).

4.3 Properties on Binary Constraints

Property 3 is central for providing a GAC filtering algorithm based on the count, for each B-coherent value in a domain, of the minimum and maximum number of C-stretches in complete instantiations. Given SEQ BIN(N, X, C, B), we focus on binary constraints B which guarantee that Property 3 holds.

Definition 3. [Van Hentenryck et al., 1992] A binary constraint F is monotonic if and only if there exists a total ordering ≺ of values in domains such that: for any value v and any value w, vFw holds implies v′Fw′ holds for all valid tuple such that v′≺ v and w≺ w′ .

Binary constraints <, >, ≤ and ≥ are monotonic, as well as the universal constraint true.

Property 4. Consider SEQ BIN(N, X, C, B) such that all non B-coherent values have been removed from domains of variables in X. B is monotonic if and only if for any variable xi ∈ X, 0 ≤ i < n - 1, for any values v1, v2 ∈ D(xi), there exists w ∈ D(xi+1) such that v1Bw and v2Bw.

Proof. (⇒) FromDefinition 3 and since we consider only Bcoherent values, each value has at least one support on B. Moreover, from Definition 3, {w | v2Cw} ⊆ {w | v1Cw} or {w | v1Cw} ⊆ {w | v2Cw}. The property holds. (⇐) Suppose that the second proposition is true and B is not monotonic. From Definition 3, if B is not monotonic then ∃v1 and v2 in the domain of a variable xi ∈ X such that, by considering the constraint B on the pair of variables (xi, xi+1), neither {w | v2Cw} ⊆ {w | v1Cw} nor {w | v1Cw} ⊆ {w | v2Cw}. Thus, there exists a support v1Bw such that (v2,w) is not a support on B, and a support v2Bw′ such that (v1, w′ ) is not a support on B. We can have D(xi+1) = {w, w′ }, which leads to a contradiction with the second proposition. The property holds.

4.4 Feasibility

From Property 4, this section provides an equivalence relation between the existence of a solution for SEQ BIN and the current variable domains of X and N. Without loss of generality, in this section we consider that all non B-coherent values have been removed from domains of variables in X. First, Definition 2 entails the following necessary condition for feasibility.

Proposition 1. Given SEQ BIN(N,X,C,B), if s(X) > max(D(N)) or s(X) < min(D(N)) then SEQ BIN fails.

D(N) can be restricted to [s(X), s(X)], but D(N) may have holes or may be strictly included in [s(X), s(X)]. We have the following proposition.

Proposition 2. Consider SEQ BIN(N,X,C,B) such that B is monotonic, with X = [x0, x1, . . . , xn-1]. For any integer k in [s(X), s(X)] there exists v in D(x0) such that k ∈ [s(x0, v), s(x0, v)].

Proof. Let v1 ∈ D(x0) a value such that s(x0, v1) = s(X). Let v2 ∈ D(x0) a value such that s(x0, v2) = s(X). By Property 4, either n = 1 or ∃w ∈ D(x1) such that v1Bw and v2Bw. Thus, from Property 3, ∀k ∈ [s(X), s(X)], either k ∈ [s(x0, v1), s(x0, v1)] or k ∈ [s(x0, v2), s(x0, v2)].

Thus, any value for N in D(N) ∩ [s(X), s(X)] is generalized arc-consistent.

Proposition 3. Given an instance of SEQ BIN(N,X,C,B) such that B is monotonic, SEQ BIN(N,X,C,B) has a solution if and only if [s(X), s(X)] ∩D(N) ̸= ∅.

Proof. (⇒) Assume SEQ BIN(N,X,C,B) has a solution. Let I[{N} ∪ X] be such a solution. By Lemmas 1 and 2, the number of C-stretches I[N] belongs to [s(X), s(X)]. (⇐) Let k ∈ [s(X), s(X)] ∩ D(N) (not empty). From Proposition 2, for any value k in [s(X), s(X)], ∃v ∈ D(x0) such that k ∈ [s(x0, v), s(x0, v)]. By Definition 2 and since Lemmas 1 and 2 consider only B-coherent values, there is a solution of SEQ BIN(N, X, C, B) with k C-stretches.

4.5 Necessary and Sufficient Filtering Condition

Given SEQ BIN(N, X, C, B), Proposition 3 can be used to filter the variable N from variables in X. Propositions 1 and 2 ensure that every remaining value in [s(X), s(X)] ∩ D(N) is involved in at least one solution satisfying SEQ BIN. We consider now the filtering of variables in X.

Proposition 4. Given SEQ BIN(N,X,C,B) such that B is monotonic, let v be a value in D(xi), i ∈ [0, n - 1]. The two following propositions are equivalent:

1. v is B-coherent and v is GAC with respect to SEQ BIN

Proof. If v is not B-coherent then, by Definition 2, v is not GAC. Otherwise, p(xi, v) (resp. s(xi, v)) is the exact minimum number of C-stretches among B-coherent instantiations I[x0, x1, . . . , xi] (resp. I[xi, xi+1, . . . , xn-1]) such that I[xi] = v. Thus, by Lemma 1 (and its symmetrical for prefixes), the exact minimum number of C-stretches among Bcoherent instantiations I[x0, x1, . . . , xn-1] such that I[xi] = v is p(xi, v) + s(xi, v) - 1. Let D(i,v) ⊆ D such that all domains in D(i,v) are equal to domains in D except D(xi) which is reduced to {v}. We call X(i,v) the sequence of variables associated with domains in D(i,v). By construction p(xi, v) + s(xi, v) - 1 = s(X(i,v)). By a symmetrical reasoning, p(xi, v)+s(xi, v)-1 = s(X(i,v)). By Proposition 3, the proposition holds.

The "- 1" in expressions p(xi, v) + s(xi, v) - 1 and p(xi, v) + s(xi, v) - 1 prevents us from counting twice a C-stretch at an extremity xi of the two sequences [x0, x1, . . . , xi] and [xi, xi+1, . . . , xn-1].

5 GAC Filtering Algorithm

Based on the necessary and sufficient filtering condition of Proposition 4, this section provides an implementation of the GAC filtering algorithm for SEQ BIN(N, X, C, B) with a monotonic constraint B.

If B /∈ {≤,≥,<,>,true} then the total ordering ≺ entailing monotonicity of B is not the natural order of integers. In this case, if ≺ is not known, it is necessary to compute such an ordering with respect to all values in ∪i∈[0,n-1](D(xi)), once before the first propagation of SEQ BIN. Consider that the two variables of B can take any value in ∪i∈[0,n-1](D(xi)): Due to the inclusion of sets of supports of values (see Definition 3), the order remains the same when the domains of the variables constrained by B do not contain all values in ∪i∈[0,n-1](D(xi)).

To compute ≺, the following procedure can be used: Count the number of supports of each value, in O(d2 ) time (recall d is the maximum domain size of a variable in X), and sort values according to the number of supports, in O(| ∪i∈[0,n-1] (D(xi))|log(| ∪i∈[0,n-1] (D(xi))|)) time.

Then, given the sequence of variables X, the algorithm is decomposed into four phases:

• ➀ Remove all non B-coherent values in the domains of X.
• ➁ For all values in the domains of X, compute the minimum and maximum number of C-stretches of prefixes and suffixes.
• ➂ Adjust the minimum and maximum value of N with respect to the minimum and maximum number of C-stretches of X.
• ➃ Using the result phase ➁ and Proposition 4, prune the remaining B-coherent values.

With respect to phase ➀, recall that B is monotonic: According to ≺, for any pair of variables (xi, xi+1), ∃v0 in D(xi) such that ∀vj ∈ D(xi), vj ̸= v0, vj has a set of supports on B(xi, xi+1) included in the supports of v0 on B(xi, xi+1). By removing from D(xi+1) non supports of v0 on B(xi, xi+1) in O(|D(xi+1)|), all non B-coherent values of D(xi+1) with respect to B(xi, xi+1) are removed. By repeating such a process in the two directions (starting from the pair (xn-2, xn-1) and from the pair (x0, x1)), all non B-coherent values can be removed from domains in O(ΣDi) time complexity.

To achieve phase ➁ we use Lemmas 1 and 2 and their symmetrical formulations for prefixes. Without loss of generality, we focus on the minimum number of C-stretches of a value vj in the domain of a variable xi, i < n-1, thanks to Lemma 1. Assume that for all w ∈ D(xi+1), s(xi+1, w) has been computed. If there is no particular property on C, the supports Sj ∈ D(xi+1) of vj on C(xi, xi+1) ∧ B(xi, xi+1) and the subset ¬Sj ∈ D(xi+1) of non-supports of vj on C(xi, xi+1) which satisfy B have to be scanned, in order to determine for each set a value w ∈ Sj minimizing s(xi+1, w) and a value w′ ∈ ¬Sj minimizing s(xi+1,w′ ) + 1. This process takes O(|D(xi+1)|) for each value, leading to O(d2 ) for the whole domain. Since all the variables need to be scanned and for all the values in domains the quantities are stored, phase ➁ takes O(nd2 ) in time, and O(ΣDi) in space.

Phases ➂ and ➃ take O(ΣDi) time each since all the domains have to be scanned. By Proposition 4, all the non-GAC values have been removed after this last phase.

If B ∈ {≤,≥,<,>,true}, ≺ is known. The worst-case time and space results come from Phase ➁. The bottleneck stems from the fact that, when a domain D(xi) is scanned, the minimum and maximum number of C-stretches of each value are computed from scratch, while an incremental computation would avoid to scan D(xi+1) for each value in D(xi). This observation leads to Property 5. Again, we focus on the minimum number of C-stretches on suffixes. Other cases are symmetrical.

Notation 2. Given SEQ BIN(N, X, C, B), xi ∈ X, 0 ≤ i < n and a value vj ∈ D(xi), if i < n- 1, let Vj denote the set of integer values such that a value s(vj , w) ∈ Vj corresponds to each w ∈ D(xi+1) and is equal to:

• s(xi+1, w) if and only if w ∈ Sj
• s(xi+1, w) + 1 if and only if w ∈ ¬Sj

Within notation 2, the set Vj corresponds to the minimum number of stretches of values in D(xi+1) increased by one if they are non supports of value vj with respect to C.

Property 5. Given SEQ BIN(N,X,C,B) such that B ∈ {≤ ,≥,<,>,true} and xi ∈ X, 0 ≤ i < n - 1, if the computation of minw∈D(xi+1)(s(vj,w)) for all vj ∈ D(xi) can be performed in O(|D(xi+1)|) time then GAC can be achieved on SEQ BIN in O(ΣDi) time and space complexity.

Proof. Applying Lemma 1 to the whole domain D(xi) takes O(|D(xi+1)|) time. Storing the minimum number of stretches for each value in D(xi) requires O(|D(xi)|) space. Phase ➁ takes O(ΣDi) space and O(ΣDi) time.

When they are represented by SEQ BIN, all the practical constraints mentioned in the introduction satisfy a condition that entails Property 5: Given xi, it is possible to compute in O(|D(xi+1)|) the quantity minw∈D(xi+1)(s(v0,w)) for a first value v0 ∈ D(xi) and then, following the natural order of integers, to derive with a constant or amortized time complexity the quantity for the next value v1, and then the quantity for the next value v2, and so on. Thus, to obtain GAC in O(ΣDi) for all these constraints, we specialize Phase ➁ in order to exploit such a property. We now detail how to proceed.

When SEQ BIN represents CHANGE, SMOOTH or INCREASING NVALUE, computing minw∈D(xi+1)(s(v0,w)) for the minimum value v0 = min(D(xi)) (respectively the maximum value) can be performed by scanning the minimum number of C-stretches of values in D(xi+1).

We now study for CHANGE, SMOOTH and INCREASING NVALUE how to efficiently compute the value minw∈D(xi+1)(s(vk,w)) of vk ∈ D(xi), either directly or from the previous value minw∈D(xi+1)(s(vk-1,w)), in order to compute minw∈D(xi+1)(s(vj , w)) for all vj ∈ D(xi) in O(|D(xi)|) time and therefore achieve Phase ➁ in O(ΣDi).

The CHANGE constraint

Section 3 showed a reformulation of CHANGE(N,X,CTR) as SEQ BIN(N ′ , X, C,true) ∧ [N = N ′ -1], where C is the opposite of CTR.

- If C is '=' then for each vj ∈ D(xi) there is a unique potential support for C on xi+1, the value vj. Therefore, by memorizing once the value vmin1 in D(xi+1) which corresponds to the smallest minimum numbers of C-stretches on the suffix starting at xi+1: ∀vj, minw∈D(xi+1)(s(vj,w)) = min(s(xi+1, vj), s(xi+1, vmin1) + 1), assuming s(xi+1, vj) = +∞when vj /∈ D(xi+1).

- If C is '̸=' then for each vj ∈ D(xi) there is a single non support. By memorizing the two values vmin1 and vmin2 which minimize the minimum numbers of C-stretches on the suffix starting at xi+1, for any value vj minw∈D(xi+1)(s(vj,w)) is equal to: min(s(xi+1, vmin1) + 1, s(xi+1, vmin2)) when vmin1 = vj, and s(xi+1, vmin1) otherwise.

- If C is '>' (the principle is similar for '≤','≥' and '<'), we introduce two quantities lt(vj, xi+1) and geq(vj, xi+1) respectively equal to minw∈[min(D(xi)),vj[(s(xi+1,w)) and minw∈[vj,max(D(xi))](s(xi+1,w)). The computation is performed in three steps:

1. Starting from v0 = min(D(xi)), that is, the value having the smallest number of supports for C on xi+1, compute lt(vj, xi+1) in increasing order of vj. Taking advantage that, given a value vj-1 ∈ D(xi) and the next value vj ∈ D(xi), [min(D(xi)), vj-1[ is included in [min(D(xi)), vj[. Therefore, the computation of all minw∈[min(D(xi)),vj[(s(xi+1,w)) can be amortized over D(xi+1). The time complexity for computing lt(vj, xi+1) for all vj ∈ D(xi) is in O(|D(xi)| + |D(xi+1)|).
2. Similarly starting from v0 = max(D(xi)), compute incrementally geq(vj, xi+1) in decreasing order of vj, in O(|D(xi)| + |D(xi+1)|).
3. Finally, for each vj ∈ D(xi), minw∈D(xi+1)(s(vj,w)) is equal to min(lt (vj , xi+1), geq(vj , xi+1) + 1).

Since step 3. takes O(D(xi)), we get an overall time complexity for Phase ➁ in O(ΣDi).

The SMOOTH constraint

It is a variant of CHANGE(N,X,CTR), where xi CTRxi+1 is |xi - xi+1| > cst, cst ∈ N that can be reformulated as SEQ BIN(N ′ ,X,C,true) ∧ [N = N ′ - 1], where C is |xi - xi+1| ≤ cst . Assume v0 = min(D(xi)) and we scan values in increasing order. Supports of values in D(xi) for |xi - xi+1| ≤ cst define a set of sliding windows for which both the starts and the ends are increasing sequences (not necessarily strictly). Thus, minw∈Sj (s(vj , w)) can be computed for all vj in D(xi) in O(|D(xi)|) thanks to the ascending minima algorithm. 1 Given a value vj ∈ D(xi) the set ¬Sj of non supports of vj on |xi - xi+1| ≤ cst is partitioned in two sequences of values: a first sequence before the smallest support and a second sequence after the largest support. While scanning values in D(xi) these two sequences correspond also to sliding windows on which the ascending minima algorithm can also be used.

The INCREASING NVALUE constraint

It is represented by SEQ BIN(N,X,=,≤). Since B is not true, we have to take into account B when evaluating minw∈D(xi+1)(s(j, w)) for each vj ∈ D(xi). Fortunately, we can start from v0 = max(D(xi)) and consider the decreasing order since B is '≤'. In this case the set of supports on B can only increase as we scan D(xi). We follow the same idea used for CHANGE(N,X,=), except that the quantity vmin1 now represents the values in D(xi+1) which corresponds to the smallest minimum numbers of C-stretches only on supports of the current value vj ∈ D(xi) on B. Since the set of supports on B only increases, vmin1 can be updated for each new value in D(xi) in O(1).

1 See http://home.tiac.net/∼cri/2001/slidingmin.html

6 RelatedWork

Using automata, CHANGE and SMOOTH can be represented either by REGULAR [Pesant, 2004] or by COST-REGULAR [Demassey et al., 2006]. In the first case this leads to a GAC algorithm in O(n2d2 ) time [Beldiceanu et al., 2010a, pages 584-585, 1544-1545] (where d denotes the maximum domain size). In the second case the filtering algorithm of COSTREGULAR does not achieve GAC.

Bessi`ere et al. [Bessi`ere et al., 2008] presented an encoding of the CARDPATH constraint with SLIDE2. A similar reformulation can be used for encoding SEQ BIN(N,X,C,B). Recall that SLIDEj(C, [x0, x1, . . . , xn-1]) holds if and only if C(xij, . . . , xij+k-1) holds for 0 ≤ i ≤ n-k j . Following a schema similar to the one proposed in Section 4 of Bessi`ere et al. paper, SEQ BIN(N, X, C, B) can be represented by adding a variable N ′ and n variables [M0, . . . ,Mn-1], with M0 = 0 and Mn-1 = N ′ . SEQ BIN(N,X,C,B) is then reformlated by SLIDE2(C ′ , [M0, x0,M1, x1, . . . ,Mn-1, xn-1]) ∧ [N ′ = N - 1], where C ′ = [¬C(xi, xi+1) ∧ B(xi, xi+1) ∧Mi+1 = Mi + 1] ∨ [C(xi, xi+1) ∧ B(xi, xi+1) ∧ Mi+1 = Mi]. According to Section 6 of Bessi`ere et al. paper, GAC can be achieved thanks to a reformulation of SLIDE2, provided a complete propagation is performed on C ′ , which is the case because B(xi, xi+1) and C(xi, xi+1) involve the same variables. The reformulation requires n additional intersection variables (one by sub-sequence [Mi, xi]), on which O(n) compatibility constraints between pairs of intersection variables and O(n) functional channelling constraints should hold. Arity of C ′ is k = 4 and j = 2: the domain of an intersection variable contains O(dk-j ) = O(d2 ) values (corresponding to binary tuples), where d is the maximum size of a domain. Enforcing GAC on a compatibility constraint takes O(d3 ) time, while functional channelling constraint take O(d2 ), leading to an overall time complexity O(nd3 ) for enforcing arc-consistancy on the reformulation, corresponding to GAC for SEQ BIN. To compare such a time complexity O(nd3 ) with our algorithm, note that O(ΣDi) is upper-bounded by O(nd).

At last, some ad hoc techniques can be compared to our generic GAC algorithm, e.g., a GAC algorithm in O(n3m) for CHANGE [Hellsten, 2004, page 57], where m is the total number of values in the domains of X. Moreover, the GAC algorithm for SEQ BIN generalizes to a class of counting constraints the ad-hoc GAC algorithm for INCREASING NVALUE [Beldiceanu et al., 2010b] without degrading time and space complexity in the case where SEQ BIN represents INCREASING NVALUE.

7 Conclusion

Our contribution is a structural characterization of a class of counting constraints for which we come up with a general polytime GAC filtering algorithm, and a characterization of the property which makes such an algorithm linear in the sum of domain sizes. A still open question is whether it would be possible or not to extend this class (e.g., considering n-ary constraints for B and C) without degrading complexity or giving up on GAC, in order to capture more constraints.