One shortcoming of Maruyama's constraint-based parser is that it requires a word to have a single part of speech; however, many words in the English language have more than one lexical category. This assumption is captured in the way that Maruyama writes constraints involving category information; the category is determined based on the position of the word in the sentence. However, even in our simple example, the word dog could have been either a noun or a verb prior to the propagation of syntactic constraints. Since parsing can be used to lexically disambiguate the sentence, ideally, the parsing algorithm should not require that the part of speech for the words be known prior to parsing.
Lexically ambiguous words can easily be accommodated by creating a CSP for each possible combination of lexical categories; however, this would be combinatorially explosive. In contrast, using a MUSE CSP, we can create a separate word node for each legal part of speech of a word, sharing those words that are not ambiguous across all segments. Since position does not uniquely define the category of a word, we must allow category information to be accessed through the role value rather than the position of the word in the sentence (i.e., use (cat x) rather than (cat (pos x))). Once we associate category information with a role value, we could instead create role values for each lexical category for a word and store all of the values in a single word node. However, this representation is not as convenient as the MUSE CSP representation for the problem. In the lexically augmented CSP, when there is more than one role per word (this is usually the case), the role values associated with one lexical category for one role cannot support the role values associated with another lexical category in another role for the same word. Additional constraints must be propagated to enforce this requirement. The MUSE CSP representation does not suffer from this problem. By using a separate node for each part of speech, the MUSE CSP directly represents the independence of the alternative lexical categories for a given word. The space requirements for the arc matrices in the MUSE representation is lower than for the lexicalized CSP as there is no arc between the roles for the different lexical categories for a word in the MUSE representation. Note that MUSE arc consistency is equivalent to performing arc consistency on the lexically augmented CSP (after the additional constraints are propagated) 2. Most importantly, MUSE CSP can represent lattices that cannot be combined into a single CSP.
The technique of creating separate nodes for different instances of a word can also be used to handle feature analysis (like number and person) in parsing [Harper & Helzerman, 1995b]. Since some words have multiple feature values, it is often more efficient to create a single node with a set of feature values, apply syntactic constraints, and then split the node into a set of nodes with a single feature value prior to applying the constraints pertaining to the feature type. Node splitting can also be used to support the use of context-specific constraints [Harper & Helzerman, 1995b].