A propagator derived from a bounds(Z)-complete propagator and a hull-injective but not hull-surjective view is only bounds(R)-complete. This is exactly what we would expect from a propagator for linear equations, as the next example demonstrates.

Example 4 (Linear constraints) A propagator for a linear constraint c∑ = J∑
n i=1 xi =
cK and n scale views (see Example 3) yield a propagator for a linear constraint with coefficients c∑a = J∑
n i=1 aixi = cK.

The usual propagator for a linear constraint with coefficients achieves bounds(R)
consistency in linear time O(n) [15]. However, it is bounds(Z)-complete for unit coefficients. Hence, the above-mentioned property applies: The propagator for c∑ is bounds(Z)-complete, scale views are only hull-injective, so the derived propagator for c∑a is bounds(R)-complete. Implementing the simpler propagator without coefficients and deriving the variant with coefficients yields propagators with exactly the same runtime complexity and propagation strength as manually implemented propagators. ∗

## 3.4 Additional Properties Of Derived Propagators

This section discusses how views can be composed, and how derived propagators behave with respect to idempotency and subsumption.

View composition. A derived propagator permits further derivation. Consider a propagator p and two views ϕ,ϕ
′. Then ϕb′(ϕb(p)) is a perfectly acceptable derived propagator, and properties like correctness and completeness carry over transitively.

For instance, we can derive a propagator for Jx−y = cK from a propagator for Jx+y =
0K, combining an *offset view* (ϕy(v) = v+c) and a *minus view* (ϕ
′y
(v) = −v) on y. This yields a propagator for Jx+ (−(y+c)) = 0K = Jx−y = cK.

Fixed points. Schulte and Stuckey [33] show how to optimize the scheduling of propagators that are known to be at a fixed point. Views preserve fixed points of propagators, so the same optimizations apply to derived propagators.

Proposition 4 Let p be a propagator, let ϕ be a view, and let d be a domain. If ϕ(d)
is a fixed point of p, then d is a fixed point of ϕb(p). ∗
Proof. Assume p(p(ϕ(d))) = p(ϕ(d)). We have to show ϕb(p)(d) = ϕb(p)(ϕb(p)(d)).

With the assumption, we can write ϕb(p)(d) = (ϕ
− ◦ p ◦ p ◦ ϕ)(d). We know that ϕ ◦ϕ
−(c) = c if |ϕ
−(c)| = |c|. As we first apply ϕ, this is the case here, so we can add ϕ ◦ϕ
− in the middle, yielding (ϕ
− ◦ p◦(ϕ ◦ϕ
−)◦ p◦ϕ)(d). With function composition being associative, this is equal to ϕb(p)(ϕb(p)(d)).

Subsumption. A propagator is *subsumed* (also known as entailed) by a domain d if and only if for all stronger domains d
′ ⊆ d, p(d
′) = d
′. Subsumed propagators cannot do any pruning in the remaining subtree of the search, and can therefore be removed. Deciding subsumption is coNP-complete in general, but for many practically relevant propagators an approximation can be decided easily (such as when a domain becomes assigned). The following theorem states that the approximation is also valid for the derived propagator.

Proposition 5 Let p be a propagator and let ϕ be a view. The propagator ϕb(p) is subsumed by a domain d if and only if p is subsumed by ϕ(d). ∗