The worst-case running time of the routine to initialize the MUSE PC-1 data
structures (in Figure 32) is O 
,
where n is the number of
nodes in a MUSE CSP and l is the number of labels.
Given that the number of (i,j) elements in E is O 
and the
domain size is O(l), there are
O 
entries in the Counter array for which to
determine the number of supporters, requiring
O(l) work; hence, initializing the Counter array requires
O 
time. Additionally, there are O S
sets to determine, each with O(l) values, so
the time required to initialize them is O .
Determining each Prev-Support[(i,j),k,a,b] and Next-Support[(i,j),k,a,b]
requires O(n) time, so the time required to calculate
all Prev-Support and Next-Support sets is O 
.
Finally, the time needed to calculate all Local-Next-Support
and Local-Prev-Support sets is O because
there are O 
sets with up to O(n) elements per set.
The worst-case running time for the algorithm which enforces MUSE
path consistency (in Figures 33 and 34) also operates
in O time.
Clearly there are O entries in the Counter array to keep track of in the
algorithm. Each Counter[(i,j),k,a,b] can be at most l in magnitude, and it can
never become negative, so the maximum running time for lines
4 and 5
in Figure 33 (given that elements, because of M, appear on the list only once)
is O . Because there are O Prev-Support
and Next-Support lists, each up to O(n) in size, the maximum running time
required to eliminate O(n) elements from those support sets is O . Finally, since there are
O Local-Next-Support and Local-Prev-Support sets from
which to eliminate
O(n) elements, the worst-case time to eliminate items from the
local sets is O . Hence, the worst-case running time of the MUSE CSP path consistency
algorithm is O .
The space complexity of MUSE CSP PC-1 is also O
because the arrays Counter and M contain O elements and
there are O S sets, each containing O(l) items;
O Prev-Support and Next-Support sets, each containing O(n) items; and
O Local-Next-Support and Local-Prev-Support sets, each containing
O(n) items.
By comparison, the worst-case running time and space complexity for
CSP path consistency, PC-4, is O . Note that for applications where 
is
representable as planar DAG or l=n, the worst-case running times of
the algorithms are the same order. If we compare MUSE CSP
to the use of multiple CSPs for problems where
are k alternative variables for a particular variable in a
CSP, then MUSE CSP path consistency can be asymptotically more
attractive, as shown in Table 2.
Table 2: Comparison of the space and time complexity for MUSE path consistency
on a MUSE CSP to path consistency on multiple CSPs representing a
node splitting problem (e.g., lexical ambiguity in parsing).
Because the proof of correctness for MUSE PC-1 is similar to our proof
for MUSE AC-1, we will only briefly outline the proof here.
A binary constraint looses support in MUSE PC-1 (see
lines 16 and 25 in Figure 34)
only if its Local-Prev-Support set or its Local-Next-Support set
becomes empty (see lines 15 and 24 in Figure 34, respectively). In
either case, it is inadmissible in any MUSE path
consistent instance. We prove that a constraint's local support sets become empty if
and only if it cannot participate in a MUSE path consistent
instance of MUSE CSP. This is proven for Local-Next-Support
(Local-Prev-Support follows by symmetry). Observe that if 
, and all of the nodes which immediately follow i (and
similarly j) in the DAG are incompatible with the truth of the constraint, then it
cannot participate in a MUSE path consistent instance. In line
23 of Figure 34, (i,k) is removed
from the Local-Next-Support[(i,j),a,b] only after
[(i,j),k,a,b] has been popped off List. The removal of (i,k)
from Local-Next-Support[(i,j),a,b] indicates that the segment
containing i, j, and k does not support 
. It
remains to be shown that [(i,j), k, a, b] is put on List only if
must be false for every segment which contains
i, j, and k. This can be proven by induction on the number of
iterations of the while loop in Figure 33
(much like the proof for MUSE AC-1).
We must also show that if = 1 after MUSE PC-1, then
it is MUSE path consistent. For
to be MUSE path consistent,
there must exist at least one path from start to end which
goes through nodes i and j such that all nodes n on that path
contain at least one label consistent with the constraint.
This proof would
be similar to the second half of the proof for MUSE AC-1 correctness.
From this, we may conclude that MUSE PC-1 builds the largest MUSE path
consistent structure.