To demonstrate the utility of MUSE CSP for simultaneously parsing
multiple CSP instances, consider the problem of determining which
strings of length 3n consisting of a's, b's, and c's are in the
language anbncn. For the value of n=3, this
problem can be represented as the single MUSE CSP problem shown in
Figure 9 (the roles and role values are not depicted
to simplify the figure).
We have devised constraints for this language (see Figure 10)
which eliminate all role values for all sentences not in the language
as well as all ungrammatical role values for a sentence in the language.
When these constraints are applied followed by MUSE arc
consistency to a lattice like that in Figure
9 with a length divisible by three, then only the grammatical
sentence will remain with a single parse. For lattices containing only
sentences with lengths that are not divisible by three, all role values are
eliminated by MUSE arc consistency (there is no grammatical sentence).
Hence, there is no search required to extract a parse if there is one.
For the n=3 case of Figure 9, the parse appears in Figure 11.
A single parse will result regardless of the n chosen.
Note that the modifiees for the role values in the parse are used to ensure that
for each a, there is a corresponding c; for each b, there is a
corresponding a; and for each c, there is a corresponding b.
Figure 12 examines the time needed to extract a
parse for sentences in the language anbncn from MUSE CSPs
representing all strings of length 3n, 
, containing a, b, and c.
The time to perform MUSE AC-1 and extract the solution is compared to
the time to extract the solution without any preprocessing.
The time to perform MUSE AC-1 and extract the parse is stable as sentence length
grows, but the time to extract a parse grows quickly for sentence lengths greater than 15
when MUSE arc consistency is not used.
Figure 9: A single MUSE CSP can simultaneously test all possible orderings of
a's, b's, and c's for membership in the language
anbncn, n=3.
Figure 10: 
= 
accepts the language anbncn, n 
0.
Figure 11: The single parse remaining in the network depicted in
Figure 9 after the applying the constraints in and enforcing
MUSE arc consistency.
Figure 12: This graph depicts the time to extract the parse
for the language anbncn from a MUSE CSP representing all
sentences of length 3n, where n varies from 1 to 7. The
time to extract the parse without MUSE arc consistency is compared
to the time to perform MUSE AC-1 and extract the parse.
The previous example involves a grammar where there can only
be one parse for a single sentence in the lattice; however, it
is a simple matter to provide similar
demonstrations for more complex cases. For example,
the constraint grammar shown in Figure 13 can be
to parse all possible sentences of a given length in the the language
ww, such that w is in 
. Consider the
MUSE CSP in Figure 14 (the roles and role values are
not depicted to simplify the figure). After applying the constraints and
performing MUSE arc consistency on this MUSE CSP,
there are precisely 81 strings that are in ww, and their
parses are compactly represented in the constraint network. The
constraints plus MUSE arc consistency eliminate every
value that cannot appear in a parse. For lattices containing
odd length sentences, no role values remain after MUSE arc consistency.
Figure 15 shows the time needed to extract all of the
parses for sentences in the language ww from the MUSE CSPs as
we vary the length of w from 1 to 8.
The time to perform MUSE AC-1 and extract the parses grows
slowly as sentence length increases because the number of parses
increases with sentence length; however, it grows
more slowly than the time to extract the parses
when MUSE arc consistency is not used.
Figure 13: 
= 
accepts the language ww.
Figure 14: A single MUSE CSP can simultaneously test all possible orderings of
a's, b's, and c's for membership in the language ww where |w|=4 .
Figure 15: This graph depicts the time to extract all parses
for the language ww from a MUSE CSP representing all
sentences of length 2 to 16 such that 
. The
time to extract all parses without MUSE arc consistency is compared
to the time to perform MUSE AC-1 and extract all parses.
Similar results have also been obtained with grammars used to parse word graphs constructed from spoken sentences in the resource management and ATIS domains [Harper, Jamieson, Zoltowski, & Helzerman, 1992, Zoltowski, Harper, Jamieson, & Helzerman, 1992, Harper & Helzerman, 1995a].