2. The set of operators affecting v**, i.e., Λ**v.

3. The maximally possible (but still reasonable) number of times that predecessors of v can change their values, i.e., FMaxReq(w1)**, . . . ,** FMaxReq(wk).

4. The actual scheduling of the value changes of the predecessors of v.
The last point is crucial - it means that in order to determine FMaxReq(v**) we should find** a particular scheduling of the value changes of pred(v**) that allows such a maximal number**
of value changes for v. The corresponding interleaving sequence of v**'s values, starting and** finishing by v 0 and v
∗**respectively, with** FMaxReq(v) value changes will be called **maximal**
and will be denoted by σ(v) (|σ(v)| = FMaxReq(v**) + 1).**
From Lemma 1, for 1 ≤ i ≤ k**, we have** FMaxReq(wi) ≤ n**, thus the number of different**
orderings of value changes of pred(v) can be exponential in n**. For instance, when, for**
1 ≤ i ≤ k**, we have** FMaxReq(wi) = n**, this number of different orderings can be expressed**
as:
k

$$\prod_{i=1}^{k-1}\sum_{j=1}^{n}{\binom{n-1}{j-1}}{\binom{n i+1}{j}}\gg2^{n k}$$

where the correctness of the expression on the left side of the inequality is shown by Lemma 4
(see Appendix B, p. 347). Clearly, we cannot check all these orderings in a naive manner.

Following, we provide an algorithm that determines σ(v**) in time which is polynomial in** n.

For clarity of presentation we want to distinguish between the different elements of a maximal sequence σ(v**). Since all variables are binary, we denote the initial value of** v, v 0, by bv and the opposite value by wv (black/white). Similarly, bi and wi **will stand for the**
corresponding values of the variable vi**. If so, we can think about all the operators in Λ**
as described in this language. Likewise, we sequentially number the appearances of each value of v on σ(v**). For example,** b ivstands for the ith appearance of the value bv **along**
σ(v). To illustrate this notation, suppose that D(v) = {true, f alse}**, the initial value of** v is v 0 = true**, and** FMaxReq(v**) = 4. Then, we have:**

$$\begin{array}{r c l}{{\mathbf{b}_{v}}}&{{\equiv}}&{{t r u e}}\\ {{\mathbf{w}_{v}}}&{{\equiv}}&{{f a l s e}}\\ {{\sigma(v)}}&{{=}}&{{\mathbf{b}_{v}^{1}\cdot\mathbf{w}_{v}^{1}\cdot\mathbf{b}_{v}^{2}\cdot\mathbf{w}_{v}^{2}\cdot\mathbf{b}_{v}^{3}}}\end{array}$$

First, for every variable v, every operator A ∈ Λv **is extended to a set of operators that**
explicitly specify prevail values for all parents of v **in the causal graph: If** |pred(v)| = k, and the prevail condition of A **is specified only in terms of some 0** ≤ k
′ ≤ k **parents**4 of v, then A **is extended to a set of 2**k−k
′
operators, where each operator extends A **by an**
instantiation of the previously unspecified parents of v**. For example, consider a variable** v with pred(v) = {u, w}**, and an operator**

$A=\{$pre : $\{b_{v}\}$, post : $\{w_{v}\}$, $\mbox{\rm{pv}}:\{b_{u}\}\}$,