In conclusion, MUSE CSP can be used to efficiently represent several similar instances of the constraint satisfaction problem simultaneously. If multiple instances of a CSP have some common variables with the same domains and compatible constraints, then they can be combined into a single instance of a MUSE CSP, and much of the work required to enforce node, arc, and path consistency need not be duplicated across the instances, especially if the constraints are sufficiently tight.
We have developed a MUSE CSP constraint-based parser, PARSEC [Harper & Helzerman, 1995a, Harper, Jamieson, Zoltowski, & Helzerman, 1992, Zoltowski, Harper, Jamieson, & Helzerman, 1992], which is capable of parsing word graphs containing multiple sentence hypotheses. We have developed syntactic and semantic constraints for parsing sentences, which when applied to a word graph, eliminate those hypotheses that are syntactically or semantically incorrect. For our work in speech processing, the MUSE arc consistency algorithm is very effective at pruning the incompatible labels for the individual CSPs represented in the composite structure. When extracting each of the parses for sentences remaining in the MUSE CSP after MUSE AC-1, it is usually unnecessary to enforce arc consistency on the CSP represented by that directed path through the network because of the tightness of the syntactic and semantic constraints.
Speech processing is not the only area where segmenting the signal into higher-level chunks is problematic. Vision systems and handwriting analysis systems have comparable problems. In addition, problems that allow for parallel alternative choices for the type of a variable, as in parsing lexically ambiguous sentences, are also excellent candidates for MUSE CSP.
C++ implementations of the algorithms described in this paper are available at the following location: ftp://transform.ecn.purdue.edu/pub/speech/harper_code/. This directory contains a README file and a file called muse_csp.tar.Z.